De luchtvaartmaatschappij werd opgericht en begon te vliegen in augustus 1993. Ze werd opgericht door International Joint Stock Aviation Company URGA, die zich in het begin richtte op chartervluchten. Reguliere passagiersvluchten van Kiev en Kryvy Rih begonnen in mei 1997. Air Urga is bezit van het Staatseigendom Fonds Oekraïne (51%) en de Lyktos Group of Companies (47%).