De militaire luchtvaart in Skopje is ouder dan het land zelf. De Engelstalige Wikipedia meldt dat Servische militaire piloten hier in 1912, tijdens de Balkanoorlogen, de eerste landing uitvoerden en dat Duitse en Bulgaarse vliegtuigen in de Eerste Wereldoorlog gebruik maakten van een vliegveld in Skopje. In 1928 werd een burgerluchthaven geopend in wat nu de wijk Aerodrom is; de huidige luchthaven werd na de Tweede Wereldoorlog gebouwd nabij Petrovec. Deze chronologie strookt niet helemaal met het verslag van dezelfde encyclopedie uit april 1941, waarin de 63e bommenwerpergroep van de Koninklijke Joegoslavische Luchtmacht, vliegend met Dornier Do 17K's, gestationeerd is op "vliegveld Petrovec nabij Skopje". Welk vliegveld dat precies was, wordt hier niet duidelijk.

Tijdens de Joegoslavische periode was Skopski Petrovac een basis voor jachtbommenwerpers. Wikipedia vermeldt dat de 98e Luchtvaartbrigade daar in de jaren 80 gestationeerd was, met het 241e squadron op de J-22 Orao, het 247e op de Jastreb en het 354e op de IJ-21 verkenningsvliegtuig Jastreb, plus een helikoptereenheid van de 2e Legerregio. In 1992 verhuisde het 241e squadron naar Lađevci in Servië. Toen Macedonië onafhankelijk werd, waren de straaljagers verdwenen; geen van deze eenheidsgegevens kon worden geverifieerd aan de hand van een officiële bron.

Het leger dateert de oprichting van zijn luchtmacht van een presidentieel decreet van 10 april 1992, waarmee een Commando Luchtmacht en Luchtverdediging werd opgericht met een luchtvaartbrigade, een luchtdoelraketregiment, een radarregiment en een luchtmachtbasis. De eerste vlucht, op 10 juni 1992, duurde 20 minuten, van 10:15 tot 10:35, in een UTVA-75 die geleend was van de vliegclubs, boven het oefenterrein van Dračevo; 10 juni is nog steeds de dag van de oprichting van de luchtmacht. De geschiedenis van het leger vermeldt dat de vluchten moesten worden gecoördineerd met de civiele verkeerstoren in Petrovec.

Helikopters kwamen als eerste, omdat dat het enige was wat een klein, door een embargo getroffen leger kon krijgen. De eerste Mi-17 arriveerde op 28 juni 1994 vanuit Oekraïne en het 301e Transporthelikoptereskader werd ermee geactiveerd; volgens Wikipedia hadden de vier Mi-17's aanvankelijk civiele registraties vanwege het VN-wapenembargo. Op 5 juli 1994 vloog een volledig Macedonische bemanning voor het eerst in een Mi-17. Zlin 242-trainingshelikopters volgden vanuit Tsjechië (1996 volgens het legerverslag, 1995 volgens Wikipedia), en één ervan ging verloren nabij Radoviš op 7 april 1999.

Het gewapende conflict tussen regeringsstrijdkrachten en het etnisch-Albanese Nationale Bevrijdingsleger duurde, volgens Wikipedia, van 22 januari tot het Kaderakkoord van Ohrid op 13 augustus 2001. De regering reageerde met een noodprogramma voor de aanschaf van gevechtsvliegtuigen. Wikipedia vermeldt vier Mi-8MT's en twee Mi-24V's uit Oekraïne op 23 maart, twee UH-1H's uit Griekenland, nog meer Mi-24's op 15 april, 15 juni en 4 september, en vier Su-25's in juni; de geschiedenis van het leger bevestigt dat er tussen maart en september Mi-8's, UH-1H's, Mi-24's, Mi-24K's en Su-25's zijn aangekomen.

Op 23 juni 2001, tijdens de gevechten bij Aračinovo aan de rand van Skopje, stegen Su-25's op vanaf Petrovec om het dorp te verkennen; Wikipedia spreekt elkaar tegen over het aantal vluchten: één of twee toestellen vlogen. Het artikel over de Luchtbrigade noemt het de eerste keer dat een Macedonisch gevechtsvliegtuig vanaf een Macedonische luchtmachtbasis opereerde. Dezelfde bron meldt dat, hoewel de opstandelingen Stinger- en Strela-2M-raketten bezaten, er geen vliegtuigen verloren gingen door grondvuur; het enige verlies betrof een Mi-17 bij Popova Šapka in maart. De aantallen slachtoffers tijdens het conflict zijn omstreden en zijn afkomstig van de betreffende dienstpagina, niet van de basis.

Door de vrede werden de straaljagers onbetaalbaar. De Su-25's werden in 2004 uit de vaart genomen en onbruikbaar op de luchthaven geparkeerd. In april 2010, toen de regering de luchthaven overdroeg aan de Turkse exploitant TAV voor reconstructie, gaf het leger de aanbouw van het commandogebouw, een fotolab, het pilotenrestaurant, werkplaatsen en de soldatenclub op; de grote hangars werden gesloopt en het nieuwe platform voor de passagiersterminal bevindt zich nu op die plek.

De oorlog in Oekraïne maakte een einde aan de rest. Minister van Defensie Slavjanka Petrovska bevestigde op 14 maart 2023 dat de vier Su-25's naar Oekraïne waren gegaan; twaalf Mi-24's volgden, waarvan er volgens één Oekraïense bron nog maar twee actief waren. Wat overblijft is een Mi-8/17-eskader dat het Tsjechische bedrijf LOM Praha in juli 2025 weer in dienst hielp nemen, een trainingseskader en een contract dat in maart 2024 werd getekend voor vier AW149's en vier AW169M's ter waarde van bijna € 250 miljoen. De gevechtsdekking komt nu van Griekenland: op 9 december 2021 onderschepten twee F-16's van de Griekse luchtmacht een Learjet van de regering boven de luchthaven ter gelegenheid van de toetreding van Noord-Macedonië tot de NAVO-luchtbewaking.