O Chipre nunca teve um caça, e a Base Aérea Andreas Papandreou não foi construída para mudar isso. Ela foi construída para que os aviões gregos pudessem pousar. A base surgiu da Doutrina de Defesa Conjunta que Nicósia e Atenas assinaram em 1993, e está localizada no lado nordeste do Aeroporto Internacional de Pafos, compartilhando a pista civil. O Cyprus Mail noticiou que os empreiteiros a entregaram à equipe técnica do Ministério da Defesa em 24 de janeiro de 1998 “sem qualquer cerimônia”, e que ela foi “projetada para servir aeronaves militares gregas”.

O presidente Glafcos Clerides propôs que a base fosse nomeada em homenagem a Andreas Papandreou, o falecido primeiro-ministro grego que, juntamente com Clerides, lançou a doutrina de defesa. O ministro da Defesa, George Charalambides, classificou-a como "claramente uma obra defensiva" para uso apenas em caso de ataque a Chipre. O líder cipriota turco, Rauf Denktash, ameaçou "quebrar as asas" de qualquer aeronave que decolasse dali, e o Ministério das Relações Exteriores da Turquia afirmou que levaria o assunto ao Secretário-Geral da ONU e ao Conselho de Segurança.

A base comprovou sua utilidade em cinco meses. Um C-130 grego pousou na segunda-feira, 15 de junho de 1998, e por volta das 10h do dia seguinte, quatro F-16 gregos aterrissaram; todas as cinco aeronaves partiram para a Grécia antes das 14h. O Cyprus Mail observou que Pafos também havia sido designada como sede dos mísseis russos S-300, que então deveriam ser instalados na ilha. O ministro da Defesa, Yiannakis Omirou, afirmou que o pouso comprovou que a base estava “operacionalmente pronta” e transmitiu uma mensagem política sobre a doutrina com a Grécia.

O Ministério das Relações Exteriores da Turquia classificou o uso da base por aeronaves gregas como “um desenvolvimento extremamente grave e provocativo”. Dois dias depois, por volta do meio-dia de 18 de junho, seis caças F-16 turcos pousaram no aeródromo de Lefkoniko, no norte da ilha; Denktash descreveu a ação como “mera restauração do equilíbrio na ilha”. Os mísseis S-300 nunca chegaram a Pafos: segundo a Wikipédia em inglês, citando o jornal The Guardian de 30 de dezembro de 1998, os mísseis foram enviados para Creta.

O que a base adquiriu foi o poderio mais pesado do Comando Aéreo. A Wikipédia em inglês afirma que Chipre comprou doze novos helicópteros de ataque Mi-35P, números de série 811 a 822, da Rússia entre 2001 e 2002. A Aeroflight indica que o Esquadrão 450 estava baseado em Pafos desde maio de 2002, quando o antigo Esquadrão de Helicópteros e Hidroaviões foi dividido em dois, com os Mi-35P juntamente com os dois aviões de treinamento PC-9 e, até 2012, um único BN-2 Islander.

Os helicópteros Hind nunca foram uma opção viável para uma força insular pequena. Em 5 de julho de 2006, um deles caiu logo após deixar a base, matando os dois tripulantes. Em 2022, o Chipre encomendou seis Airbus H145M, com opção para mais seis, para substituir os onze Mi-35 restantes, e a AP noticiou que a Sérvia estava interessada em comprá-los; os dois primeiros H145M foram entregues em 26 de março de 2025. A localização da base dos novos helicópteros não é informada nas fontes consultadas. A Wikipédia em inglês também afirma que os helicópteros antitanque Gazelle foram transferidos para lá quando a base de Lakatamia foi fechada em abril de 2013, uma informação baseada em um site de entusiastas e contradita pela Aeroflight.

Na década de 2020, a base tornou-se um ponto de apoio para aeronaves de terceiros. Oito caças Hawk sauditas e dois C-130 reabasteceram em voo no local em 26 de maio de 2023. Em 23 de janeiro de 2025, uma equipe de avaliação de resposta a contingências da Força Aérea dos EUA visitou a base para estudar melhorias nas operações aeroportuárias, logística e comunicações. Washington ofereceu-se para cobrir parte ou a totalidade dos custos; o governo insistiu que a base permaneceria sob controle cipriota.

Quando drones de fabricação iraniana atacaram a região em março de 2026, o terminal do aeroporto de Pafos foi evacuado em 2 de março, após um objeto suspeito ter aparecido no radar, e o porta-voz adjunto do governo afirmou em 3 de março que não havia aeronaves americanas na base. A Grécia enviou caças F-16 no mesmo mês. O Cyprus Mail, citando o Proto Thema, noticiou em maio que dois caças seriam estacionados em Pafos, e em agosto o ministro da Defesa, Vasilis Palmas, confirmou que eles estavam operando a partir da Base Aérea Andreas Papandreou, de acordo com os protocolos bilaterais vigentes, ressaltando, porém, que o destacamento era temporário.