The airline was established on 4 October 1995 (1995-10-04) as a wholly owned commercial subsidiary of the Gromov Flight Research Institute and named Gromov Air, which was registered on 10 October the same year. In its beginnings the carrier operated cargo flights only; regular scheduled passenger services commenced in 2000. The airline was renamed Moskovia Airlines in 2006. Russian-manufactured aircraft (An-12s, An-24s, Tu-134s, Tu-154s and Yak-40s) made up the fleet until 2009, when leasedBoeing 737s were phased in. The Sukhoi Superjet 100 was incorporated into the fleet in 2013.
Moskovia Airlines filed for bankruptcy in February 2014 but planned to continue its operations. Delays with flights returning passengers from the Montenegrin resort of Tivat and also with services from Astrakhan to Turkey were revealed in mid-July 2014 (2014-07); at this time, it was informed the airline was unable to pay for the fuel. An inspection that came after these delays resulted in the Russia's Federal Air Transport Agency Rosaviatsia suspending the commercialisation of tickets and the airline shrinking its operations to serve just the Moscow–Tivat route. That month, it was reported that the company would apparently continue its operations as a charter airline. In August 2014 (2014-08), Rosaviatsia suspended the Moskovias's air operator's certificate (AOC) following the carrier's CEO stating the carrier could no longer operate due to financial difficulties. One of the causes for the suspension of the AOC responded to the fact that Moskovia did not meet the Russian regulations for the minimum number of aircraft to operate scheduled passenger services. After three months of suspension, the AOC was finally cancelled in December 2014 (2014-12).