The airline was formed in 1963 as Arkhangelsk United Aviation Squadron (Russian: Архангельский объединенный авиационный отряд) and became AVL Arkhangelsk Airlines (Russian: Архангельские воздушные линии) in 1991. In August 2004 Aeroflot acquired 51% of the airline, with the rest being held by Aviainvest. The company was renamed Aeroflot-Nord, becoming Aeroflot's second regional airline. It joined the European Regions Airline Association in December 2006.
As the contract with Aeroflot ceased on 1 December 2009, the airline operates since then independently as Nordavia. Reasons for the retreat of Aeroflot were the bad press the subsidiary received following the Aeroflot Flight 821 disaster, and the decision of Russian aviation officials dating from 15 July 2009, to impose restrictions (including ban on international charter tours) on then Aeroflot-Nord flight operations due to insufficient security and bad finances.