Üsküp'teki askeri havacılık, ülkenin kuruluşundan daha eskidir. İngilizce Wikipedia'ya göre, Sırp askeri pilotları Balkan Savaşları sırasında 1912'de burada ilk inişi gerçekleştirmiş ve Alman ve Bulgar uçakları Birinci Dünya Savaşı'nda Üsküp'teki bir alanı kullanmıştır. Sivil bir havaalanı, günümüzde Aerodrom bölgesi olarak bilinen yerde 1928'de açılmıştır; mevcut havaalanı ise İkinci Dünya Savaşı'ndan sonra Petrovec yakınlarında inşa edilmiştir. Bu kronoloji, aynı ansiklopedinin Nisan 1941 tarihli anlatımıyla çelişmektedir; bu anlatıma göre, Dornier Do 17K uçaklarıyla uçan Yugoslav Kraliyet Hava Kuvvetleri'nin 63. Bombardıman Grubu, "Üsküp yakınlarındaki Petrovec havaalanında" bulunuyordu. Hangi havaalanı olduğu burada kesin olarak belirtilmemiştir.

Yugoslavya döneminde Skopski Petrovac bir savaş uçağı üssüydü. Wikipedia'ya göre, 1980'lerde burada 98. Havacılık Tugayı, J-22 Orao kullanan 241. filo, Jastreb kullanan 247. filo ve IJ-21 keşif uçağı Jastreb kullanan 354. filo ile 2. Ordu bölgesine bağlı bir helikopter birliği bulunuyordu. 1992'de 241. filo Sırbistan'daki Lađevci'ye taşındı. Makedonya bağımsızlığını kazandığında jetler gitmişti; bu birlik detaylarının hiçbiri resmi bir kaynakla karşılaştırılamadı.

Ordu, hava kuvvetlerinin kuruluşunu 10 Nisan 1992 tarihli bir cumhurbaşkanlığı kararnamesine dayandırır; bu kararnameyle bir havacılık tugayı, bir hava savunma roket alayı, bir radar alayı ve bir hava üssünden oluşan bir Hava Kuvvetleri ve Hava Savunma Komutanlığı kurulmuştur. İlk uçuşu, 10 Haziran 1992'de, havacılık kulüplerinden ödünç alınan bir UTVA-75 ile Dračevo eğitim bölgesi üzerinde 10:15 ile 10:35 arasında 20 dakika sürmüştür; 10 Haziran hala Hava Kanadı'nın günü olarak kabul edilir. Ordu tarihçesinde, uçuşlarının Petrovec'teki sivil kontrol kulesiyle koordine edilmesi gerektiği belirtilmektedir.

Helikopterler ilk gelenlerdi çünkü küçük ve ambargo altındaki bir ordunun elde edebileceği tek şey onlardı. İlk Mi-17, 28 Haziran 1994'te Ukrayna'dan geldi ve 301. Nakliye Helikopter Filosu onunla birlikte faaliyete geçti; Wikipedia'ya göre, BM silah ambargosu nedeniyle dört Mi-17 başlangıçta sivil tescilli olarak uçuyordu. 5 Temmuz 1994'te tamamen Makedon mürettebatı ilk kez bir Mi-17 uçurdu. Çek Cumhuriyeti'nden Zlin 242 eğitim helikopterleri geldi (Ordunun kayıtlarında 1996, Wikipedia'da 1995) ve bunlardan biri 7 Nisan 1999'da Radoviš yakınlarında kayboldu.

Wikipedia'nın tarihlemesine göre, hükümet güçleri ile etnik Arnavut Ulusal Kurtuluş Ordusu arasındaki silahlı çatışma, 22 Ocak'tan 13 Ağustos 2001 tarihli Ohrid Çerçeve Anlaşması'na kadar sürdü. Hükümet, acil bir satın alma programıyla karşılık verdi. Wikipedia, 23 Mart'ta Ukrayna'dan dört Mi-8MT ve iki Mi-24V, Yunanistan'dan iki UH-1H, 15 Nisan, 15 Haziran ve 4 Eylül'de daha fazla Mi-24 ve Haziran ayında dört Su-25 helikopteri listeliyor; Ordunun tarihçesi ise Mart ve Eylül ayları arasında Mi-8'ler, UH-1H'ler, Mi-24'ler, Mi-24K'lar ve Su-25'lerin geldiğini doğruluyor.

23 Haziran 2001'de, Üsküp'ün kenarındaki Aračinovo'daki çatışmalar sırasında, Su-25'ler Petrovec'ten havalanarak köyü keşfe çıktı; Wikipedia'daki anlatımlar bir veya iki uçağın uçtuğu konusunda farklılık gösteriyor. Hava Tugayı makalesi, bunun bir Makedon sabit kanatlı savaş uçağının bir Makedon hava üssünden ilk kez operasyon yapması olduğunu belirtiyor. Aynı kaynak, isyancıların Stinger ve Strela-2M füzelerine sahip olmasına rağmen, hiçbir uçağın yer ateşinden dolayı kaybedilmediğini; tek kaybın Mart ayında Popova Šapka'da bir Mi-17 olduğunu söylüyor. Çatışmaya ilişkin kayıp rakamları tartışmalıdır ve üsse değil, hizmet sayfasına aittir.

Barış, jetleri karşılanamaz hale getirdi. Su-25'ler 2004 yılında hizmetten çekildi ve uçamaz halde havaalanında park edildi. Nisan 2010'da hükümet havaalanını yeniden inşa için Türk işletmeci TAV'a devrettiğinde, Ordu komuta binasının ek binasını, fotoğraf laboratuvarını, pilot restoranını, atölyeleri ve asker kulübünü teslim etti; büyük hangarları yıkıldı ve yolcu terminalinin önündeki yeni apron şimdi onların yerinde bulunuyor.

Ukrayna savaşı geri kalanını da halletti. Savunma Bakanı Slavjanka Petrovska, 14 Mart 2023'te dört Su-25'in Ukrayna'ya gittiğini doğruladı; ardından on iki Mi-24 geldi, ancak bir Ukrayna kaynağına göre bunlardan sadece ikisi hala aktif durumdaydı. Geriye kalanlar ise Çek firması LOM Praha'nın Temmuz 2025'te tekrar hizmete sokmasına yardımcı olduğu bir Mi-8/17 filosu, bir eğitim filosu ve Mart 2024'te imzalanan yaklaşık 250 milyon avro değerinde dört AW149 ve dört AW169M sözleşmesi. Savaş uçağı desteği artık Yunanistan'dan geliyor: 9 Aralık 2021'de Yunan Hava Kuvvetleri'ne ait iki F-16, Kuzey Makedonya'nın NATO hava polisliğine girişini kutlamak için havaalanı üzerinde bir hükümet Learjet'ini önledi.