The airline was founded as Sakha Avia, the former Aeroflot Yakutsk Division and also previously known as Yakutaviatrans. It also operated cargo charters to Africa, Asia, Europe and the Middle East until it filed for bankruptcy in early 1999. It emerged in 2000 and is controlled by the regional government, Neryungri State Air Enterprise. It merged with Yakutavia in 2002 and changed its name to Yakutia Airlines.
On 4 February 2010, Flight 425, operated by Antonov An-24 RA-47360 suffered an engine failure on take-off from Yakutsk Airport for Olekminsk Airport. During the subsequent landing, the nose and port main undercarriage were retracted, causing substantial damage to the aircraft.