Кипр никогда не владел истребителями, и авиабаза имени Андреаса Папандреу была построена не для того, чтобы это изменить. Она была построена для того, чтобы греческие самолеты могли совершать посадку. База возникла в рамках Доктрины совместной обороны, подписанной Никосией и Афинами в 1993 году, и расположена на северо-восточной стороне международного аэропорта Пафоса, используя общую гражданскую взлетно-посадочную полосу. Газета Cyprus Mail сообщила, что подрядчики передали ее техническому персоналу министерства обороны 24 января 1998 года “без каких-либо церемоний”, и что она была “предназначена для обслуживания греческой военной авиации”.

Президент Глафкос Клеридес предложил назвать его в честь Андреаса Папандреу, покойного премьер-министра Греции, который вместе с Клеридесом разработал оборонительную доктрину. Министр обороны Георгий Хараламбидес назвал его “явно оборонительным сооружением”, предназначенным для использования только в случае нападения на Кипр. Лидер турецких киприотов Рауф Денкташ пригрозил “сломать крылья” любому самолету, взлетевшему с него, а министерство иностранных дел Турции заявило, что вынесет этот вопрос на рассмотрение Генерального секретаря ООН и Совета Безопасности.

База доказала свою эффективность в течение пяти месяцев. В понедельник, 15 июня 1998 года, приземлился греческий самолет C-130, а около 10 часов утра следующего дня совершили посадку четыре греческих F-16; все пять самолетов вылетели в Грецию до 14:00. Газета Cyprus Mail отметила, что Пафос также был назначен местом базирования российских ракет С-300, которые должны были быть доставлены на остров. Министр обороны Яннакис Омиру заявил, что посадка доказала “оперативную готовность” базы и дала ей политический сигнал относительно доктрины в отношении Греции.

Министерство иностранных дел Турции назвало использование базы греческой авиацией “крайне серьезным и провокационным событием”. Два дня спустя, около полудня 18 июня, шесть турецких F-16 приземлились на аэродроме Лефконико на севере; Денкташ охарактеризовал это как “просто восстановление равновесия на острове”. Системы С-300 так и не прибыли в Пафос: согласно английской Википедии, ссылающейся на The Guardian от 30 декабря 1998 года, ракеты были направлены на Крит.

База получила самое мощное вооружение в составе командования ВВС. Английская Википедия утверждает, что Кипр закупил у России двенадцать новых ударных вертолетов Ми-35П с серийными номерами от 811 до 822 в 2001–2002 годах. По данным журнала Aeroflight, 450-я эскадрилья базировалась в Пафосе с мая 2002 года, когда старая вертолетно-гидросамолетная эскадрилья была разделена на две части: Ми-35П, два учебно-тренировочных самолета PC-9 и, до 2012 года, один BN-2 Islander.

Вертолеты «Хинд» никогда не были удобным вариантом для небольшого островного флота. 5 июля 2006 года один из них разбился вскоре после вылета с базы, погибли оба члена экипажа. В 2022 году Кипр подписал соглашение о закупке шести вертолетов Airbus H145M с опцией на еще шесть, чтобы заменить одиннадцать сохранившихся Ми-35, и агентство AP сообщило, что Сербия заинтересована в их приобретении; первые два H145M были поставлены 26 марта 2025 года. Место базирования новых вертолетов в проверенных источниках не указано. Английская Википедия также утверждает, что противотанковые вертолеты «Газель» были переведены сюда после закрытия Лакатамии в апреле 2013 года, однако это утверждение основано на любительском сайте и противоречит данным Aeroflight.

В 2020-х годах база стала перевалочным пунктом для самолетов других стран. 26 мая 2023 года здесь дозаправились восемь саудовских самолетов Hawk и два C-130. 23 января 2025 года базу посетила группа оценки мер реагирования ВВС США для изучения возможности модернизации аэропорта, логистики и связи; Вашингтон предложил покрыть часть или все расходы, но правительство настаивало на том, что база останется под контролем Кипра.

Когда в марте 2026 года иранские беспилотники нанесли удар по региону, 2 марта терминал аэропорта Пафоса был эвакуирован после того, как на радаре появился подозрительный объект, а заместитель пресс-секретаря правительства 3 марта заявил, что на базе нет американских самолетов. В том же месяце Греция направила F-16. В мае Cyprus Mail со ссылкой на Proto Thema сообщила, что два таких самолета будут размещены в Пафосе, а в августе министр обороны Василис Пальмас подтвердил, что они вылетают из аэропорта Андреас-Папандреу в соответствии с существующими двусторонними протоколами, подчеркнув при этом, что развертывание носит временный характер.