The airline was formed in Akureyri by Tryggvi Helgason as Norðurflug, and was incorporated as Flugfélag Norðurlands on 1 May 1975. A reorganisation and merger of Icelandair Domestic and Norlandair (Flugfélag Norðurlands) 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. Upon delivery of these aircraft, Air Iceland sold its only Dash 8-100 series. It previously operated ATR 42 aircraft from 2000 to 2003. A fleet of 3 Bombardier Dash 8-Q400 aircraft will replace the airline's 5 Fokker F50 aircraft in 2015-16. Services using the new aircraft will include a route to Aberdeen on behalf of Icelandair due to start in March 2016.
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.