Năm 1962 mục sư Eilif Krogager và Jørgen Størling lập hãng hàng không thuê bao Sterling Airways. Lúc đầu hãng mua 2 máy bay cánh quạt loại Douglas DC-6B của Swissair và bay thuê bao tuyến đường Scandinavia - Địa Trung Hải. Chuyến bay đầu tiên tới Las Palmas (Tây Ban Nha).
Năm 1965 hãng mua các máy bay phản lực đầu tiên, loại Caravelle. Do đó Sterling Airways là hãng hàng không thuê bao có đội máy bay hiện đại lớn nhất thế giới.
Năm 1968, Sterling Airways được mua khỏi Hãng du lịch Tjæreborg và trở thành công ty độc lập.
Năm 1987, công ty mừng kỷ niệm sinh nhật thứ 25. Năm này công ty có 19 máy bay và 1.300 nhân viên.
Năm 1994, tái lập công ty dưới tên Sterling European Airlines với 3 máy bay và 182 nhân viên.
Năm 1996, công ty tàu thủy Fred. Olsen của Na Uy mua Sterling European Airlines
Năm 2000, hãng có tuyến bay thường xuyên tới Málaga và Alicante (Tây Ban Nha) thay cho các chuyến thuê bao du lịch.
Năm 2001, hãng tách khỏi ngành hàng không thuê bao du lịch và trở thành hãng hàng không giá hạ với nhiều tuyến đường ở châu Âu.
Năm 2002, hãng mở thêm 21 tuyến đường mới giữa vùng Scandinavia tới Nam Âu và Copenhagen - Oslo - Stockholm.
Năm 2003, hãng tăng cường đội máy bay từ 6 lên 8 chiếc và mở thêm 11 tuyến đường tới Nam Âu. Số hành khách đạt tới 1,3 triệu, tăng 40% so với năm 2002.
Năm 2004, hãng có đội máy bay 12 cái.
Tháng 3 năm 2005, công ty Fred.Olsen bán Sterling Airlines cho công ty đầu tư Fons Eignarhaldsfelag của Iceland, chủ của hãng hàng không nhỏ Iceland Express. Tháng 6 năm 2005 Fons Eignarhaldsfelag mua công ty Maersk Air của Tập đoàn A.P.Moller-Maersk. Tới tháng 9 năm 2005 thì Sterling Airlines và Maersk Air hợp nhất thành Sterling Airlines A/S, hãng hàng không giá hạ lớn thứ tư châu Âu. Chỉ một tháng sau, Fons Eignarhaldsfelag lại bán hãng này cho Tập đoàn FL (trụ sở ở Reykjavík, Iceland).
27 tháng 12 năm 2006, Tập đoàn FL bán hãng này cho Nordic Travel Holding, công ty cổ phần do 3 công ty FL, Eignarhaldsfelag và Sons làm chủ.
13 tháng 4 năm 2007, hãng LD Equity 2 mua Ban bảo trì máy bay của Sterling và lập ra Essential Aircraft Maintenance Services A/S.