The airline was formed in Akureyri by Tryggvi Helgason as Nordurflug, and was incorporated as Flugfelag Nordurlands on 1 May 1975. A reorganisation and merger of Icelandair Domestic and Norlandair (Flugfélag Nordurlands) resulted in the present name in 1997. It is wholly owned by Icelandair Group and had 226 employees in March 2007.
In late 2011 Air Iceland acquired two Bombardier Dash 8-200 aircraft for delivery in early 2012. The aircraft will be fitted with improvements such as extra fuel tanks, renovated cabin interiors and a new advanced glass cockpit. Upon delivery of these aircraft, Air Iceland sold its only Dash 8-100 series. It previously operated ATR 42 from 2000 to 2003.
On 4 March 2011, as Dash 8 TF-JMB was landing at the Nuuk Airport it was hit by a microburst and the right wheel broke off causing the aircraft to slide off the runway. All 31 people on board were unharmed. However, the aircraft was written off.