Pafos FC was founded on 10 June 2014, after the merger of AEK Kouklia and AEP Paphos. In the 2013–14 season, AEK Kouklia competed in the Cypriot First Division for the first time in their history, but got relegated at the end of the season. The same season, AEP Paphos (which were created after the merger of the two clubs of Paphos, APOP and Evagoras) were competing in the Cypriot Second Division, but were facing huge economic problems and were constantly punished with point deductions. After the 2013–14 season finished, discussions began between the two clubs to create a new club for the Paphos district, in order to have a healthy and economically competitive team.
On 9 June 2014, the two clubs in a separate general meeting approved the creation of the new team, Pafos FC. On 10 June 2014, was held the first meeting of the fans of the new team, with the presence of political persons and football players from Paphos. The first chairman of the new team was Christakis Kaizer, who was the president of AEK Kouklia and one of the protagonists of the effort to create the new club. The new team uses the Geroskipou Stadium in Geroskipou.
The logo of Pafos FC is a variation of AEP Paphos's logo, including the team name and 2014 as the year of establishment, and the figure of the hero Evagoras Pallikaridis. The logo also includes the team's colors, the blue, white and yellow.