NordStar was founded by Norilsk Nickel and was launched on 17 December 2008, based on local Taimyr Peninsula airlines. NordStar replaced KrasAir as the biggest airline of Krasnoyarsky kray.
NordStar operated its first flight on 17 June 2009, from Norilsk to Moscow Domodedovo and Krasnoyarsk.
In 2010 and 2011, from Moscow, Krasnoyarsk and Norilsk, Nordstar launched flights to Saint Petersburg, Sochi, Krasnodar, Mineralnye Vody, Vladivostok, Khabarovsk, Novosibirsk, Yekatrinburg, Tomsk, Nizhnevartovsk, Surgut, Chita, Ulan-Ude, Irkutsk, Baykit, Vanavara, Tungunsk, Turukhansk, Severo-Eniseysk, Igarka, Dushanbe and Tashkent.
NordStar plans to develop a passenger loyalty program and extend its route network.