The first airport operation dates from 1925, when the one aircraft was a FrenchDornue-Comet. The present three-story airport building opened in 1965.
The airline was established in 1961 as the Mineralnye Vody Aviation Group. The first international city it operated services to was Berlin in 1980. The airport and its civil aviation service was reorganized into the Mineralnye Vody Civil Aviation Enterprise in 1988, under the direction of V.V. Babaskin. It was reorganized again in 1995 into the State United Venture Kavminvodyavia, more commonly known as KMV. The airline purchased several Tupolev Tu-204 aircraft in 1997.
Following the 2010 decision of the Russian government to transfer the assets to Aeroflot, the airline ceased operations on October 1st, 2011.