キプロスはこれまで戦闘機を所有したことはなく、アンドレアス・パパンドレウ空軍基地もそれを変えるために建設されたわけではない。ギリシャ軍の戦闘機が着陸できるように建設されたのだ。この基地は、1993年にニコシアとアテネが署名した共同防衛ドクトリンに基づいて設立され、パフォス国際空港の北東側に位置し、民間用滑走路を共有している。キプロス・メール紙は、請負業者が1998年1月24日に「何の儀式もなく」国防省の技術スタッフに基地を引き渡したこと、そして「ギリシャ軍用機の運用を目的として設計された」ことを報じた。.

グラフコス・クレリデス大統領は、同基地を、クレリデス大統領と共に防衛ドクトリンを提唱した故アンドレアス・パパンドレウ元ギリシャ首相にちなんで命名することを提案した。ゲオルギオス・チャランビデス国防相は、同基地は「明らかに防衛的な施設」であり、キプロスが攻撃された場合にのみ使用されるものだと述べた。トルコ系キプロス人指導者のラウフ・デンクタシュ氏は、同基地から離陸する航空機の「翼を折る」と脅迫し、トルコ外務省は、この問題を国連事務総長と安全保障理事会に提起すると述べた。.

この基地はわずか5ヶ月でその目的を証明した。1998年6月15日月曜日にギリシャのC-130輸送機が着陸し、翌日の午前10時頃にはギリシャのF-16戦闘機4機が着陸した。5機すべてが午後2時までにギリシャに向けて出発した。キプロス・メール紙は、パフォスが当時島に配備予定だったロシアのS-300ミサイルの拠点としても指定されていたことを指摘した。国防大臣のヤナキス・オミロウ氏は、この着陸によって基地が「作戦準備完了」であることが証明され、ギリシャに対してこのドクトリンに関する政治的なメッセージを伝えるものとなったと述べた。.

トルコ外務省は、ギリシャ軍機による同基地の使用を「極めて重大かつ挑発的な事態」と非難した。その2日後の6月18日正午頃、トルコ空軍のF-16戦闘機6機が北部のレフコニコ飛行場に着陸した。デンクタシュ氏はこれを「島内の均衡を回復したに過ぎない」と表現した。S-300ミサイルはパフォスには配備されなかった。英語版ウィキペディアによると、1998年12月30日付のガーディアン紙の記事を引用して、ミサイルは代わりにクレタ島に配備されたという。.

基地が手に入れたのは、航空司令部で最も強力な戦力だった。英語版ウィキペディアによると、キプロスは2001年から2002年にかけて、ロシアからシリアル番号811から822までの新型Mi-35P攻撃ヘリコプター12機を購入した。エアロフライト誌は、旧ヘリコプター・水上機飛行隊が2つに分割された2002年5月からパフォスに第450飛行隊を配置し、Mi-35Pは2機のPC-9練習機と、2012年までは1機のBN-2アイランダーと共に配備されたとしている。.

ハインドは、小さな島国の部隊には決して快適な装備ではなかった。2006年7月5日、1機が基地を離陸して間もなく墜落し、乗員2名が死亡した。2022年、キプロスは残存する11機のMi-35を置き換えるため、エアバスH145Mを6機契約し、さらに6機のオプション契約を結んだ。AP通信は、セルビアが購入に関心を示していると報じた。最初の2機のH145Mは2025年3月26日に納入された。新しいヘリコプターがどこに配備されているかは、確認した情報源には記載されていない。英語版ウィキペディアには、2013年4月にラカタミアが閉鎖された際にガゼル対戦車ヘリコプターがここに移動したとも書かれているが、これは趣味のサイトに基づく主張であり、エアロフライトによって否定されている。.

2020年代には、この基地は他国の航空機の中継地点となった。2023年5月26日には、サウジアラビアのホーク戦闘機8機とC-130輸送機2機がここで燃料補給を行った。2025年1月23日には、米空軍の緊急対応評価チームが空港運営、兵站、通信の改善を調査するために訪問し、ワシントンは費用の一部または全額を負担すると申し出た。政府は基地がキプロスの管理下に置かれることを主張した。.

2026年3月にイラン製のドローンが同地域を攻撃した際、レーダーに不審な物体が映ったため、3月2日にパフォス空港のターミナルが避難措置をとった。政府副報道官は3月3日、同基地にアメリカ軍機は配備されていないと述べた。ギリシャは同月にF-16を派遣した。キプロス・メール紙はプロト・テーマ紙を引用し、5月に2機がパフォスに配備されると報じ、8月にはヴァシリス・パルマス国防相が、既存の二国間協定に基づきアンドレアス・パパンドレウ空港から飛行していることを確認し、配備は一時的なものであると強調した。.