The airline was formed in 1963 as Arkhangelsk United Aviation Squadron (Russian: Архангельский объединенный авиационный отряд) and became AVL Arkhangelsk Airlines (Архангельские воздушные линии) 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.
Since the contract with Aeroflot ended on 1 December 2009, the airline has operated independently as Nordavia. Because of the bad press the subsidiary received following the Aeroflot Flight 821 disaster, and Russian aviation officials' 15 July 2009 imposition of restrictions (including a ban on international charter tours) on then Aeroflot-Nord flight operations due to insufficient security and bad finances, Aeroflot has distanced itself from Nordavia.