Vojenské letectvo ve Skopje je starší než země sama. Anglická Wikipedie uvádí, že srbští vojenští letci zde poprvé přistáli v roce 1912 během balkánských válek a že německá a bulharská letadla používala letiště ve Skopje během první světové války. Civilní letiště bylo otevřeno v roce 1928 v dnešní čtvrti Aerodrom; současné letiště bylo postaveno po druhé světové válce poblíž Petrovce. Tato chronologie se nepříliš dobře shoduje s popisem dubna 1941 ve stejné encyklopedii, která umisťuje 63. bombardovací skupinu Královského jugoslávského letectva létající na letounech Dornier Do 17K na "letiště Petrovec poblíž Skopje". Které letiště to bylo, není zde jasné.

V jugoslávských letech byl Skopski Petrovac základnou stíhacích bombardérů. Wikipedie uvádí, že v 80. letech zde byla umístěna 98. letecká brigáda s 241. letkou na letounu J-22 Orao, 247. na letounu Jastreb a 354. na průzkumném letounu IJ-21 Jastreb, plus vrtulníková jednotka 2. armádního regionu. V roce 1992 se 241. brigáda přesunula do Lađevců v Srbsku. Když Makedonie získala nezávislost, letouny byly pryč; žádný z těchto údajů o jednotce nebylo možné ověřit s oficiálním zdrojem.

Armáda datuje vznik svého letectva k prezidentskému dekretu z 10. dubna 1992, kterým bylo zřízeno Velitelství letectva a protivzdušné obrany s leteckou brigádou, raketovým plukem protivzdušné obrany, radarovým plukem a leteckou základnou. Jeho první let, 10. června 1992, trval 20 minut, od 10:15 do 10:35, v letounu UTVA-75 zapůjčeném od aeroklubů, nad výcvikovým prostorem Dračevo; 10. červen je dodnes dnem leteckého křídla. Historie armády uvádí, že její lety musely být koordinovány s civilní řídící věží v Petrovci.

Vrtulníky byly na prvním místě, protože to bylo to, co mohla malá armáda, na kterou bylo uvaleno embargo, získat. První Mi-17 dorazil z Ukrajiny 28. června 1994 a s ním byla aktivována 301. letka transportních vrtulníků; podle Wikipedie měly čtyři Mi-17 původně civilní registraci kvůli zbrojnímu embargu OSN. Dne 5. července 1994 poprvé vzlétla s Mi-17 plně makedonská posádka. Z České republiky následovaly cvičné letouny Zlin 242 (1996 podle armády, 1995 podle Wikipedie) a jeden byl ztracen poblíž Radoviše 7. dubna 1999.

Ozbrojený konflikt mezi vládními silami a etnickou albánskou Národní osvobozeneckou armádou probíhal podle datování Wikipedie od 22. ledna do Ohridské rámcové dohody ze dne 13. srpna 2001. Vláda reagovala nouzovým nákupním programem. Wikipedie uvádí čtyři Mi-8MT a dva Mi-24V z Ukrajiny z 23. března, dva UH-1H z Řecka, další Mi-24 z 15. dubna, 15. června a 4. září a čtyři Su-25 v červnu; historie armády potvrzuje, že Mi-8, UH-1H, Mi-24, Mi-24K a Su-25 dorazily mezi březnem a zářím.

Dne 23. června 2001, během bojů u Aračinova na okraji Skopje, vzlétly z Petrovce letouny Su-25, aby provedl průzkum vesnice; Wikipedie se liší v tom, zda letělo jedno nebo dvě letadla. Článek o letecké brigádě to uvádí jako první případ, kdy makedonský bojový letoun s pevnými křídly operoval z makedonské letecké základny. Stejný zdroj uvádí, že ačkoli povstalci drželi rakety Stinger a Strela-2M, žádné letadlo nebylo ztraceno palbou ze země; jedinou ztrátou byl Mi-17 v Popově Šapce v březnu. Údaje o obětech v konfliktu jsou sporné a patří na servisní stránku, nikoli na základnu.

Mír učinil letouny nedostupnými. Su-25 byly staženy z provozu v roce 2004 a na letišti zaparkovány jako nelétavé. V dubnu 2010, kdy vláda předala letiště tureckému provozovateli TAV k rekonstrukci, armáda se vzdala přístavby své velitelské budovy, fotolaboratoře, restaurace pro piloty, dílen a vojenského klubu; její velké hangáry byly zbourány a na jejich místě nyní stojí nová plocha před terminálem pro cestující.

Válka na Ukrajině zbytek vyjasnila. Ministryně obrany Slavjanka Petrovská 14. března 2023 potvrdila, že čtyři Su-25 putovaly na Ukrajinu; následovalo dvanáct Mi-24, z nichž podle jedné ukrajinské zprávy byly stále aktivní pouze dva. Zbývá jen letka Mi-8/17, kterou česká firma LOM Praha pomohla vrátit do služby v červenci 2025, cvičná letka a smlouva podepsaná v březnu 2024 na čtyři AW149 a čtyři AW169M v hodnotě téměř 250 milionů eur. Stíhací krytí nyní pochází z Řecka: 9. prosince 2021 dva letouny F-16 řeckého letectva zachytily nad letištěm vládní letoun Learjet u příležitosti vstupu Severní Makedonie do systému vzdušného provozu NATO.