Chipre nunca ha tenido un avión de combate, y la base aérea Andreas Papandreou no se construyó para cambiar eso. Se construyó para que los aviones griegos pudieran aterrizar. La base surgió de la Doctrina de Defensa Conjunta que Nicosia y Atenas firmaron en 1993, y se ubica en el lado noreste del Aeropuerto Internacional de Pafos, compartiendo la pista civil. El Cyprus Mail informó que los contratistas la entregaron al personal técnico del Ministerio de Defensa el 24 de enero de 1998 "sin ninguna ceremonia", y que fue "diseñada para servir a la aviación militar griega".

El presidente Glafcos Clerides propuso bautizarla con el nombre de Andreas Papandreou, el difunto primer ministro griego que, junto con Clerides, había impulsado la doctrina de defensa. El ministro de Defensa, George Charalambides, la calificó de “claramente una obra defensiva” destinada a ser utilizada únicamente en caso de ataque a Chipre. El líder turcochipriota Rauf Denktash amenazó con “romper las alas” de cualquier aeronave que despegara desde ella, y el Ministerio de Asuntos Exteriores turco anunció que llevaría el asunto ante el Secretario General de la ONU y el Consejo de Seguridad.

La base demostró su eficacia en cinco meses. Un C-130 griego aterrizó el lunes 15 de junio de 1998, y alrededor de las 10 de la mañana del día siguiente aterrizaron cuatro F-16 griegos; los cinco aviones habían partido hacia Grecia antes de las 2 de la tarde. El Cyprus Mail señaló que Pafos también había sido designada como base para los misiles rusos S-300 que debían llegar a la isla. El ministro de Defensa, Yiannakis Omirou, afirmó que el aterrizaje demostraba que la base estaba "operativamente preparada" y transmitía un mensaje político sobre la doctrina con Grecia.

El Ministerio de Asuntos Exteriores turco calificó el uso de la base por aviones griegos como un hecho sumamente grave y provocador. Dos días después, alrededor del mediodía del 18 de junio, seis F-16 turcos aterrizaron en el aeródromo de Lefkoniko, en el norte; Denktash lo describió como un mero restablecimiento del equilibrio en la isla. Los S-300 nunca llegaron a Pafos: según la Wikipedia en inglés, que cita a The Guardian del 30 de diciembre de 1998, los misiles fueron enviados a Creta.

Lo que sí adquirió la base fue la mayor potencia de fuego del Mando Aéreo. Según la Wikipedia en inglés, Chipre compró doce helicópteros de ataque Mi-35P nuevos, con números de serie del 811 al 822, a Rusia entre 2001 y 2002. Aeroflight sitúa al Escuadrón 450 en Pafos desde mayo de 2002, cuando el antiguo Escuadrón de Helicópteros e Hidroaviones se dividió en dos, con los Mi-35P junto a los dos aviones de entrenamiento PC-9 y, hasta 2012, un único BN-2 Islander.

Los helicópteros Hind nunca fueron adecuados para una fuerza aérea de una pequeña isla. El 5 de julio de 2006, uno se estrelló poco después de despegar de la base, causando la muerte de ambos tripulantes. En 2022, Chipre firmó un contrato para la compra de seis Airbus H145M, con opción a seis más, para reemplazar los once Mi-35 restantes. AP informó que Serbia estaba interesada en adquirirlos; los dos primeros H145M se entregaron el 26 de marzo de 2025. Las fuentes consultadas no especifican la ubicación de la base de los nuevos helicópteros. La Wikipedia en inglés también afirma que los helicópteros antitanque Gazelle se trasladaron a esta base cuando Lakatamia cerró en abril de 2013, una afirmación que proviene de un sitio web de aficionados y que Aeroflight contradice.

En la década de 2020, la base se convirtió en un punto de escala para aeronaves extranjeras. Ocho aviones Hawk saudíes y dos C-130 repostaron aquí el 26 de mayo de 2023. El 23 de enero de 2025, un equipo de evaluación de respuesta ante contingencias de la Fuerza Aérea de EE. UU. visitó la base para estudiar mejoras en las operaciones, la logística y las comunicaciones del aeropuerto. Washington se ofreció a cubrir parte o la totalidad del costo; el gobierno insistió en que la base permanecería bajo control chipriota.

Cuando drones de fabricación iraní atacaron la región en marzo de 2026, la terminal del aeropuerto de Pafos fue evacuada el 2 de marzo tras la aparición de un objeto sospechoso en el radar, y el portavoz adjunto del gobierno declaró el 3 de marzo que no había aeronaves estadounidenses en la base. Grecia envió F-16 ese mismo mes. Cyprus Mail, citando a Proto Thema, informó en mayo que dos de estos aviones estarían estacionados en Pafos, y en agosto el ministro de Defensa, Vasilis Palmas, confirmó que volaban desde Andreas Papandreou en virtud de los protocolos bilaterales vigentes, al tiempo que recalcó que el despliegue era temporal.