Koryŏ Hangkong được thành lập năm 1954 với tên ban đầu là Chosonminhang (조선민항, 朝鮮民航, Triều Tiên Dân hàng) với tư cách là người kế tục của SOKAO - hãng hàng không liên doanh Liên Xô-CHDCND Triều Tiên thành lập năm 1950[2]. Hãng bắt đầu hoạt động từ ngày 21.9.1955 với các máy bay loại Lisunov Li-2, Antonov An-2 và Ilyushin Il-12. Thập niên 1960 hãng có thêm máy bay Ilyushin Il-14 và Ilyushin Il-18 tua-bin cánh quạt.
Năm 1993 CAAK đổi tên thành Air Koryo. Cùng năm hãng đặt mua 3 máy bay Ilyushin Il-76 để chở hàng hóa tới Trung Quốc và Nga. Mới đây hãng đã đặt mua 2 máy bay Tu-204 để thay đội máy bay quốc tế cũ và cũng bắt đầu hiện đại hóa đội máy bay quốc nội.
Thế kỷ 21
Do Châu Âu lo ngại về tính an toàn và bảo trì, năm 2006 Air koryo bị thêm vào danh sách các hãng hàng không bị cấm ở Châu Âu năm 2006. Uỷ Ban Châu Âu cũng đã tìm thấy các bằng chứng về sự thiết sót an toàn nghiêm trọng của Air Koryo. AIr Koryo liên tục không giải quyết về các vấn đề về các cuộc kiểm tra tiếp theo của EU.
Tháng 9 năm 2009, Air koryo đã đặt mua một chiếc Tupolev Tu-204-300 và một chiếc Tupolev Tu-204-100, và sẽ nhận được chiếc đầu tiên trong số hai chiếc Tupolev Tu-204-100B được trang bị 210 chỗ ngồi. Các chuyến bay đến Đại Liên ở Trung Quốc được thêm vào lịch trình của Air Koryo. Ngoài ra, các chuyến bay Tu-134 một tuần từ Bình Nhưỡng và các dịch vụ trực tiếp từ Bình Nhưỡng đến Phố Đông Thượng Hải đã được khai trương với dịch vụ hai tuần một lần trên JS522 và khứ hồi trên JS523 vào năm 2010
Vào tháng 3 năm 2010, Air Koryo được phép tiếp tục hoạt động tại EU bằng máy bay Tu-204 của họ vì được trang bị các thiết bị cần thiết để tuân thủ các tiêu chuẩn quốc tế bắt buộc. Tu-204 là loại máy bay duy nhất mà Air Koryo khai thác được bay vào không phận EU. Vào tháng 4 năm 2014 Air Koryo đã khai thác dịch vụ đầu tiên đến Malaysia với việc khánh thánh từ các chuyến bay từ Bĩnh Nhưỡng đến Kuala Lumpur. Các chuyến bay được khai thác 2 tuần 1 lần bằng Tu-204, nhưng đã bị hủy giữa năm 2017 do các lệnh trừng phạt được áp dụng sau vụ đầu độc Kim Jong Nam tại sân bay quốc tế Kuala Lumpur.
Năm 2012 Air Koryo khai trương dịch vụ đến Thành phố Kuwait , được vận hành hàng tuần bằng máy bay Tu-204. Các dịch vụ này hoạt động trong mùa du lịch cao điểm – từ tháng 4 đến tháng 10.
Năm 2014, Air Koryo mở rộng tuyến đường bay sang Cáp Nhĩ Tân , Trung Quốc. Năm 2012, Juche Travel Services, một công ty điều hành các tour du lịch đến Bắc Triều Tiên, đã ra mắt các tour du lịch "dành cho người đam mê hàng không" bằng máy bay thuê bao của Air Koryo, mang đến cho du khách cơ hội bay trên mọi loại máy bay của Air Koryo trong phạm vi Bắc Triều Tiên, Mil-17, An-24, Tu-134, Tu-154 và Il-62. Các dịch vụ quốc tế được điều hành bởi An-148 , Tu-154 hoặc Tu-204.
Tính đến năm 2021, hai máy bay Tupolev Tu-204-100B khác được cho là đã chuẩn bị cho Air Koryo thuê. Tuy nhiên, cả hai đều được nhìn thấy với tên Sky KG Airlines được thêm vào trên màu sắc của Air Koryo và đã được Moscow chuyển đến Sân bay quốc tế Zhukovsky , nơi chúng vẫn ở lại cho đến tháng 11 năm 2023. Các báo cáo tình báo và phương tiện truyền thông cho thấy rằng Triều Tiên vẫn có thể đang cố gắng mua hai máy bay phản lực này với sự hỗ trợ của Nga kể từ tháng 11 năm 2023.
Tuy nhiên sau khi sửa đổi hiến pháp đầu năm 2024, Triều Tiên đã từ bỏ nỗ lực thống nhất với Hàn Quốc, trong đó có việc cắt đứt mọi liên lạc liên Triều, coi Hàn Quốc là "ngoại bang", sửa đổi lại bản đồ trên các phương tiện thông tin đại chúng, phá bỏ Cổng Thống nhất tại Bình Nhưỡng, đóng cửa tổ chức liên quan đến công tác thống nhất Triều Tiên. Biểu trưng của hãng hàng không Air Koryo cũng được thay đổi để phù hợp với Hiến pháp, khi đôi cánh được vẽ lại thành cách điệu các lớp lông vũ trên cánh chim.
Năm 2015, Air Koryo đã công bố màu sơn mới với quốc kỳ Triều Tiên được vẽ lại dưới trạng thái đang tung bay ở đuôi, cùng với một dải màu đỏ nhỏ chạy dọc trên phần bụng máy bay màu xám.
Ngày 1/7/1981 = 1 máy bay Ilyushin 62M của CAAK (tiền thân của Air Koryo) từ Bình Nhưỡng tới Conakry (Guinea) đã bị tai nạn ở vùng núi Fouta Djall (Guinea). Tất cả 23 người trên máy bay bị thiệt mạng.