Группа A.P. Moller-Maersk Group начала искать возможности для инвестиций в авиационный бизнес в середине 1960-х годов. Для компании, занимающейся грузотранспортными перевозками с начала двадцатого века, создание собственной авиакомпании выглядело естественным и логическим шагом в развитии. Группа Maersk купила в 1969 году Falck Air, выполнявшую регулярные перевозки между Копенгагеном и Оденсе. Для Maersk Air были куплены три новых самолёта Fokker F-27.
Boeing 707 был куплен в 1973 году для обслуживания чартерных перевозок на Средиземноморье; в том же году были куплены вертолёты для обслуживания нефтяных месторождений на Северном море.
Maersk купила в начале 1990-х годов 49 % акций Estonian Air; в 2003 году сделка была расторгнута.
30 июня 2005 года A.P. Moller-Maersk Group согласилась продать Maersk Air исландскому инвестиционному фонду Fons Eignarhaldsfélag, в сентябре того же года она и Sterling European Airlines слились в единую компанию Sterling Airlines.
Флот
Флот Maersk Air fleet перед слиянием в Sterling Airlines состоял из следующих судов: