The airline was established by Lebanese businessmen in 1998 and began operations in June, 2000. It was founded as an open-end joint stock company. In 2003 UM Air had over 500 employees and carried 210,000 passengers. The airline now has 640 staff. The airline operated Airbus A320 airliners in the past. In 2007, the Ukrainian Air Administration refused to renew UM Airlines' license because of safety concerns. In September, 2007 the European Commission banned Ukrainian-Mediterranean Airlines from operating in airspace over the European Union citing safety issues. This meant that it was banned for safety reasons from operating services of any kind within the European Union. In November 2009, the airline was allowed to resume operations with its McDonnell Douglas MD-83 aircraft by the European Commission.
On 26 May 2003 a UM Yak-42Dcrashed near Maçka, Trabzon (Turkey) while carrying 62 Spanish troops from Afghanistan to Zaragoza Air Base. All 75 on board died. At the time, the Spanish presence in the ISAF missions was being disputed among the Spanish politicians. There were accusations of the Ministry of Defence hiring cheap unairworthy aircraft. The scandal damaged the image of minister Federico Trillo. Furthermore, in 2004 it was revealed that the corpse identification in the Turkish mountains was rushed and several bodies were delivered to the wrong relatives.