The first airport operation was in 1925, when a FrenchDornue-Comet was the sole aircraft. The present three-story airport building opened in 1965.
The airline was established in 1961 as the Mineralnye Vody Aviation Group. Its first international destination 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 1 October 2011.