Il club fu fondato nel giugno 2014, quando fu ratificata l'unione tra l'AEK Kouklion e l'AEP Paphos. L'AEK Kouklion era reduce dal suo primo campionato disputato in A' Katīgoria concluso però con la retrocessione in seconda serie, mentre l'AEP Paphos nel corso della stessa stagione era impegnato proprio in seconda serie, ma doveva fare i conti con problemi economici e penalizzazioni in classifica. Le due squadre si sono così fuse per formare un unico club più competitivo.
Il 9 giugno 2014 i due club, al termine di altrettante assemblee separate, hanno approvato la creazione del Pafos FC. Il giorno successivo la nuova squadra è stata presentata ai tifosi, con la presenza di politici e sportivi della città. Il primo presidente è stato Christakis Kaizer, già presidente dell'AEK Kouklion. Il primo allenatore è stato invece il serbo Radmilo Ivančević, già tecnico dell'AEP Paphos anni prima tra il 2002 e il 2003. Sul logo del Pafos FC, come già avvenuto su quello dell'AEP Paphos, campeggia il volto di Evagoras Pallikarides, membro dell'organizzazione paramilitare EOKA.
Partito dalla seconda serie nazionale, il Pafos FC ha conquistato la promozione in Divisione A già al termine della sua prima stagione (2014-2015) grazie al secondo posto in classifica. La permanenza nella massima serie è durata un solo anno, vista la retrocessione arrivata dopo la poule retrocessione della A' Katīgoria 2015-2016. Nonostante ciò, il club è riuscito a tornare immediatamente nella massima serie con un ulteriore secondo posto ottenuto l'anno successivo.
Nella stagione A' Katīgoria 2023-2024 vince la Coppa di Cipro battendo in finale l'Omonia Nicosia e qualificandosi per i preliminari di Europa League; riesce poi ad entrare in Conference League.
Bianco, blu
Cipro
Juan Carlos Carcedo
Wikimedia Commons contiene immagini o altri file su Pafos Football Club
