Реформы были неминуемы и в сфере военного образования. В 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 самолетов.
В тот же период были созданы Объединенные силы быстрого реагирования (ОСБР), в состав которых вошел и авиационный компонент (на то время 3 авиаполка). Эти силы в первую очередь обеспечивались топливом, запасными частями, комплектовались военнослужащими-контрактниками. Остальные авиачасти обеспечивались уже по остаточному принципу.
В 1996-2001 гг. в составе ВВС существовала пилотажная группа “Украинские соколы», базировавшаяся на аэродроме Кировское. Первоначально она летала на L-39, а затем перешла на МиГ-29 (один из них потерян в 1998 г.). Первое публичное выступление группы состоялось 9 мая 1997 г. над Киевом. В 1997-98 гг. она выступала на авиасалонах в Чехии и Великобритании, а в 1999 и 2001 гг. снова демонстрировала групповой пилотаж над Киевом, в ходе проведения авиационных парадов. Затем группа прекратила выступления из-за отсутствия необходимого финансирования. В 1995-97 гг. существовала еще одна пилотажная группа – «Украинские казаки» на L-39. Она базировалась на аэродроме Умань и готовилась к полетам в составе 8 самолетов. Группу расформировали в связи с проблемами финансирования, а также произошедшей 17 августа 1997 г. катастрофой.
По состоянию на 2003 г. в ВВС Украины насчитывалось 392 боевых самолета, входивших в состав девяти авиаполков: четырех ИАП, двух БАП, двух ОШАП и одного ОРАП. Кроме того, в структуру входили по одному ВТАП.'УАП. ряд ОСАП и один полк ДПЛА. Тогда же начался переход с полковой на бригадную структуру, при этом в течение года из боевого состава вывели 120 самолетов.