The airline was founded as Sakha Avia, the former Aeroflot Yakutsk Division and also previously known as Yakutaviatrans. It 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 form Yakutia Airlines. 
On 4 February 2010, Flight 425, operated by an 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. No one was hurt or killed in the crash and the aircraft was subsequently repaired and placed back into service.