К концу 1993 г. расформировали 17-ю ВА, число воинских частей в ВВС уменьшилось на 88, а личного состава – на 35000 человек. В 1994 г. расформировали авиационную группу ДА, а в следующем году – ВТА. К концу 1995 г. в ВВС сократили еще 199 воинских частей, оставив два авиационных корпуса (5-й и 14-й), по одной дивизии Дальней и Военно-транспортной авиации, а также отдельные авиационные полки и эскадрильи. В первые годы независимости из состава ВВС были выведены МиГ-21, МиГ-23, L-29, Су-17МР, Як-28ПП. В целом, до конца 1996 г. сократили около 800 ЛА. В том же году из морской авиации в состав ВВС передали МиГ-29 и Су-25.
Реформы были неминуемы и в сфере военного образования. В 1993 г. началось переподчинение авиационных вузов новосозданной структуре – Харьковскому институту летчиков ВВС (ХИЛ ВВС). В результате к 1999 г. были расформированы Черниговское и Харьковское ВВАУЛ, Луганское ВВАУ штурманов. Харьковское ВВА инженерное училище, функции которых перешли к ХИЛ ВВС. Дольше всех продержался Киевский институт ВВС, однако и он в 2000 г. был объединен с ХИЛом, который получил наименование Харьковский институт ВВС. Еще через 4 года этот вуз объединили с Харьковским военным университетом, присвоив очередное новое наименование – Харьковский университет Воздушных сил им. И. Кожедуба. На фондах Киевского института ВВС был создан факультет ВВС Национальной академии обороны Украины (с 2010 г. – Национальный университет обороны Украины).
В 1996 г. Президент Украины подписал «Государственную программу развития ВС на период до 2005 года». К ее конечному сроку планировалось сократить еще 150000 человек, управления 5 авиадивизий, а также 289 самолетов (180 боевых) и 189 вертолетов (60 боевых). К 2005 г. в составе ВВС должны были остаться два авиационных корпуса, учебное авиационное командование, авиационная группа оперативного назначения, отдельные авиационные полки и авиационные базы.
После того как в 1997 г. на саммите в Мадриде Президент Украины подписал соглашение «НАТО-Украина», началась реализация планов по ориентации в военном строительстве в сторону Северо-Атлантического блока. Тем временем продолжались реформы структуры и оптимизация авиапарка ВВС. В том числе из боевого состава были выведены Ту-16, Ту-22, Ту-22М, Ту-95, Ту-160, Ан-2. В 1994-99 гг. численность ВВС сократилась со 100000 до 60000 человек, за это время расформировали 22 авиаполка, а также ряд отдельных эскадрилий. Всего за 1997- 2000 гг. было проведено более 1200 организационных мероприятий в рамках оптимизации структуры ВВС.
2000 г. стал «лебединой песней» ДА Украины. Два Ту-22М3 из 185-го ТБАП выполнили пуски ракет Х-22 в Баренцевом море, после чего начался их вывод из боевого состава и утилизация, продлившаяся до 2006 г. Надо сказать, что несколько лет, начиная с 2000 г., существовала 35-я авиационная группа оперативного назначения, которая включала полк на Ту-22М3 и полк на Ил-76. Но ее довольно быстро расформировали в связи с сокращением Ту-22М3.
В марте 2000 г. руководство МО Украины озвучило планы по выводу из боевого состава к 2005 г. еще 600 самолетов и 400 вертолетов. Сэкономленные деньги предполагалось направить на модернизацию остального парка ЛА. В 2001 г. в ВВС ликвидировали дивизионное звено. Система управления стала осуществляться по схеме «командование ВВС – авиакорпус – авиаполк». По состоянию на начало 2001 г. в составе ВВС насчитывались: одна авиационная группа, 21 авиаполк и 6 авиабаз, службу проходили 52000 человек. Тот год стал критическим в плане подготовки выпускников летных профилей в Харьковском институте летчиков: основную массу из них выпустили без летной практики и направили служить на наземные должности. Потребовалось вмешательство высшего руководства страны, чтобы решить эту проблему.
В первые годы нового тысячелетия на базе 14-го, 5-го авиакорпусов и структур ПВО создали три воздушных командования (ВзК): «Запад» (штаб – во Львове), «Центр» (Васильков), «Юг» (Одесса), а также тактическую группу «Крым» (Севастополь). В период 2000-02 гг. сократили пять авиаполков и вывели из боевого состава 170 самолетов.
