Cyprus heeft nooit een gevechtsvliegtuig bezeten en de luchtmachtbasis Andreas Papandreou is niet gebouwd om daar verandering in te brengen. De basis is gebouwd zodat Griekse vliegtuigen er konden landen. De basis is voortgekomen uit de gezamenlijke defensiedoctrine die Nicosia en Athene in 1993 ondertekenden en ligt aan de noordoostkant van de internationale luchthaven van Paphos, waar ze de civiele landingsbaan deelt. De Cyprus Mail meldde dat de aannemers de basis op 24 januari 1998 "zonder enige ceremonie" aan de technische staf van het ministerie van Defensie hadden overgedragen en dat deze "ontworpen was om Griekse militaire vliegtuigen te huisvesten".

President Glafcos Clerides stelde voor het te vernoemen naar Andreas Papandreou, de overleden Griekse premier die samen met Clerides de defensiedoctrine had ontwikkeld. Minister van Defensie George Charalambides noemde het "duidelijk een defensief bouwwerk" dat alleen gebruikt zou worden in geval van een aanval op Cyprus. De Turks-Cypriotische leider Rauf Denktash dreigde de vleugels van elk vliegtuig dat ervan opsteeg te "breken", en het Turkse ministerie van Buitenlandse Zaken liet weten de kwestie aan te kaarten bij de secretaris-generaal van de VN en de Veiligheidsraad.

De basis bewees binnen vijf maanden zijn nut. Een Griekse C-130 landde op maandag 15 juni 1998, en de volgende dag rond 10 uur 's ochtends landden vier Griekse F-16's; alle vijf vliegtuigen waren vóór 14.00 uur weer naar Griekenland vertrokken. De Cyprus Mail merkte op dat Paphos ook was aangewezen als de thuisbasis voor de Russische S-300 raketten die toen op het eiland zouden worden gestationeerd. Minister van Defensie Yiannakis Omirou zei dat de landing bewees dat de basis "operationeel gereed" was en een politieke boodschap over de doctrine richting Griekenland uitdroeg.

Het Turkse ministerie van Buitenlandse Zaken noemde het gebruik van de basis door Griekse vliegtuigen "een uiterst ernstige en provocerende ontwikkeling". Twee dagen later, rond het middaguur op 18 juni, landden zes Turkse F-16's op het vliegveld van Lefkoniko in het noorden; Denktash beschreef dit als "slechts het herstellen van het evenwicht op het eiland". De S-300's zijn nooit in Paphos terechtgekomen: volgens de Engelstalige Wikipedia, die The Guardian van 30 december 1998 citeert, gingen de raketten in plaats daarvan naar Kreta.

Wat de basis wél verwierf, was de zwaarste slagkracht van het luchtmachtcommando. Volgens Wikipedia kocht Cyprus in 2001-2002 twaalf nieuwe Mi-35P-aanvalshelikopters, serienummers 811 tot en met 822, van Rusland. Aeroflight plaatst 450 Squadron in Paphos vanaf mei 2002, toen het oude helikopter-watervliegtuigeskader in tweeën werd gesplitst, met de Mi-35P's naast de twee PC-9-trainingsvliegtuigen en, tot 2012, een enkele BN-2 Islander.

De Hind-helikopters bleken nooit echt geschikt voor een kleine eilandmacht. Op 5 juli 2006 stortte er een neer kort na het opstijgen vanaf de basis, waarbij beide bemanningsleden om het leven kwamen. In 2022 tekende Cyprus een contract voor zes Airbus H145M's, met een optie voor nog eens zes, ter vervanging van de elf overgebleven Mi-35's. AP meldde dat Servië interesse had in de aanschaf ervan; de eerste twee H145M's werden geleverd op 26 maart 2025. Waar de nieuwe helikopters gestationeerd zijn, wordt niet vermeld in de geraadpleegde bronnen. De Engelstalige Wikipedia meldt ook dat de Gazelle antitankhelikopters hierheen zijn verplaatst toen Lakatamia in april 2013 sloot, een bewering die afkomstig is van een hobbyistenwebsite en wordt tegengesproken door Aeroflight.

In de jaren twintig werd de basis een tussenstop voor vliegtuigen van anderen. Acht Saoedische Hawks en twee C-130's tankten hier bij op 26 mei 2023. Op 23 januari 2025 bracht een evaluatieteam van de Amerikaanse luchtmacht een bezoek om de mogelijkheden voor verbetering van de luchthavenactiviteiten, logistiek en communicatie te onderzoeken. Washington bood aan om een deel of alle kosten te dekken; de Cypriotische regering stond erop dat de basis onder Cypriotisch bestuur zou blijven.

Toen Iraanse drones de regio in maart 2026 aanvielen, werd de terminal van de luchthaven van Paphos op 2 maart geëvacueerd nadat een verdacht object op de radar was verschenen. De plaatsvervangend regeringswoordvoerder verklaarde op 3 maart dat er geen Amerikaanse vliegtuigen op de basis aanwezig waren. Griekenland stuurde diezelfde maand F-16's. Cyprus Mail meldde in mei, op basis van een bericht van Proto Thema, dat er twee in Paphos gestationeerd zouden worden. In augustus bevestigde minister van Defensie Vasilis Palmas dat ze vanaf Andreas Papandreou opereerden volgens de bestaande bilaterale protocollen, waarbij hij benadrukte dat de inzet tijdelijk was.