Kypr nikdy nevlastnil stíhačku a letecká základna Andrease Papandreoua nebyla postavena proto, aby to změnila. Byla postavena tak, aby na ní mohly přistávat řecké letouny. Základna vznikla na základě Společné obranné doktríny, kterou Nikósie a Atény podepsaly v roce 1993, a nachází se na severovýchodní straně mezinárodního letiště v Pafosu, kde sdílí civilní ranvej. Cyprus Mail informoval, že dodavatelé ji předali technickému personálu ministerstva obrany 24. ledna 1998 “bez špetky ceremoniálů” a že byla “navržena pro službu řeckým vojenským letadlům”.

Prezident Glafkos Clerides navrhl pojmenovat jej po Andreasu Papandreouovi, zesnulém řeckém premiérovi, který spolu s Cleridesem zavedl obrannou doktrínu. Ministr obrany George Charalambides jej označil za “jasně obranné dílo” určené k použití pouze v případě útoku na Kypr. Vůdce kyperských Turků Rauf Denktash pohrozil, že “zlomí křídla” každému letadlu, které z něj vzlétne, a turecké ministerstvo zahraničí uvedlo, že věc předloží generálnímu tajemníkovi OSN a Radě bezpečnosti.

Základna osvědčila svůj účel během pěti měsíců. V pondělí 15. června 1998 přistál řecký letoun C-130 a následující den kolem 10:00 přistály čtyři řecké stíhačky F-16; všech pět letadel odletělo do Řecka před 14:00. List Cyprus Mail poznamenal, že Pafos byl také určen jako domov ruských raket S-300, které měly být na ostrově umístěny. Ministr obrany Jannakis Omirou uvedl, že přistání prokázalo, že základna je “operačně připravena” a neslo politické poselství o doktríně s Řeckem.

Turecké ministerstvo zahraničí označilo využívání základny řeckými letadly za “extrémně závažný a provokativní vývoj”. O dva dny později, kolem poledne 18. června, přistálo na letišti Lefkoniko na severu šest tureckých stíhaček F-16; Denktash to popsal jako “pouhé obnovení rovnováhy na ostrově”. Systémy S-300 se do Pafosu nikdy nedostaly: podle anglické Wikipedie s odvoláním na deník The Guardian z 30. prosince 1998 rakety místo toho mířily na Krétu.

Základna sice získala největší úder pro velitelství letectva. Anglická Wikipedie uvádí, že Kypr v letech 2001–2002 koupil od Ruska dvanáct nových útočných vrtulníků Mi-35P, sériových čísel 811 až 822. Aeroflight umisťuje 450. letku do Pafosu od května 2002, kdy byla stará letka vrtulníků a hydroplánů rozdělena na dvě části, s vrtulníky Mi-35P vedle dvou cvičných vrtulníků PC-9 a do roku 2012 jedním BN-2 Islander.

Vrtulníky Hind se nikdy nehodily pro malou ostrovní armádu. 5. července 2006 se jeden z nich krátce po opuštění základny zřítil a obě posádky zahynuly. V roce 2022 Kypr podepsal smlouvu na šest Airbusů H145M s opcí na dalších šest, které měly nahradit jedenáct zbývajících Mi-35, a agentura AP uvedla, že o jejich koupi mělo zájem Srbsko; první dva H145M byly dodány 26. března 2025. Kde jsou nové vrtulníky umístěny, není v ověřených zdrojích uvedeno. Anglická Wikipedie také uvádí, že protitankové vrtulníky Gazelle se sem přesunuly, když byla v dubnu 2013 uzavřena Lakatamia, což je tvrzení, které vychází z webu pro amatéry a které vyvrací Aeroflight.

Ve 20. letech 21. století se základna stala zastávkou pro letadla jiných zemí. Dne 26. května 2023 zde doplnilo palivo osm letounů Saudi Hawk a dva letouny C-130. Dne 23. ledna 2025 základnu navštívil tým amerického letectva pro hodnocení reakce na mimořádné události, aby prozkoumal modernizaci letištního provozu, logistiky a komunikace, přičemž Washington nabídl úhradu části nebo všech nákladů; vláda trvala na tom, že základna zůstane pod kyperskou kontrolou.

Když v březnu 2026 zasáhly region drony íránské výroby, byl terminál letiště v Pafosu 2. března evakuován poté, co se na radaru objevil podezřelý objekt, a zástupce mluvčí vlády 3. března uvedl, že na základně nejsou žádná americká letadla. Řecko ve stejném měsíci vyslalo stíhačky F-16. Cyprus Mail s odvoláním na Proto Thema v květnu informoval, že v Pafosu budou umístěny dva letouny, a v srpnu ministr obrany Vasilis Palmas potvrdil, že létají z letiště Andreas Papandreou v rámci stávajících bilaterálních protokolů, a zdůraznil, že nasazení je dočasné.