The large number of Soviet-made former Aeroflot aircraft came to Air Ukraine upon its foundation in 1992, with most of them being phased out over the following years. When the airline was shut down in 2002, only three Tupolev Tu-134 and one Tu-154 were operational.
On 27 October 1993, the nosegear of an Air Ukraine Let L-410 Turbolet (registered UR-67536) was torn off while on the ground at Tyumen Airport when the pilots accidentally maneuvered the aircraft with eight people on board off the paved taxiway.
On 23 January 1995, another Turbolet (registered UR-67115) was destroyed when it crashed on a frozen lake whilst approaching Provedenia Airport in Russia because of an engine failure. The three crew members on board had been on an empty ferry flight from Anadyr Airport, which was planned to continue onwards to Honduras, to where the aircraft had been sold. There were no fatalities.
On 4 April of the same year, the pilots of an Air Ukraine Antonov An-26 (registered UR-26049) tried to take off from Palana Airport without having released the brakes. The aircraft thus was not able to get airborne, and overshot the runway, being damaged beyond economical repair. The nine persons that had been on the chartered flight to Ust-Pakhachi Airport survived the accident.