Unter den Königreichen des Altertums, besaß Paphos einen besonderen Status als religiöses Zentrum. Glaubte man doch, dass die „Schaumgeborene Göttin“ ihren Fuß zum ersten Mal auf dieser Insel, beim Felsen Petra tou Romiou, wenige Kilometer von Kouklia entfernt, an Land setzte.
Der Tempel von Paphos war das berühmteste Heiligtum der Aphrodite im Altertum. Und Paphos lag zur Zeit des Altertums an der Stelle des heutigen Dorfes Kouklia. Erst nachdem die Hafenstadt, Neu-Paphos 15 km weiter westlich gegründet wurde, wurde die alte Hauptstadt Paleapaphos (Alt-Paphos) genannt.

Die Ursprünge von Alt-Paphos und die des Heiligtums, reichen weit in die Frühzeit zurück. Die antike Literatur erzählt nennt zwei Ursprünge.
Die eine ist, der Tempel der Aphrodite sei vom arkadischen König Agapenor von Tega erbaut worden, nachdem er als Schiffbrüchiger auf seinem Heimweg von Troja an der Küste Zyperns landete.
Die andere nennt den sagenhaft reichen zyprischen König Kinyras, den Vater des Adonis, der zur Zeit des trojanischen Krieges uralt gewesen sein muss, als Gründer.

Bekannt ist, das Alt-Paphos bereits im 15. Jhd vor Chr. eine bedeutende Siedlung war, Gold- und Elfenbeinfunde aus der Spätbronzezeit bezeugen dies.
Die Siedlung blieb bis in die frühe Eisenzeit erhalten, denn die Ausgrabungen zeigen keinen Bruch in der Besiedlungsgeschichte.
Der erste überlieferte König der Insel wird auf einer Inschrift des assyrischen Königs Asarhaddon aus dem Jahr 673v.Chr. als tributpflichtiger König Assyriens genannt.
So wie andere griechische Städte erhob auch Paphos sich 499v.Chr gegen das Perserreich, wurde aber wieder unterworfen.

Die archaische und klassische Zeit vom 7.-4. Jhd.v.Chr. war dann der Höhepunkt in der Geschichte Alt-Paphos, bis 312 v.Chr. der letzte König von Paphos, Nikokles, Neu-Paphos als neue Hauptstadt gründete. Nach und nach verlagerte sich das wirtschaftliche und administrative Leben nach Neu-Paphos.
Nikokles verlor in den Diadochen Kriegen seine politische Macht im Ptolemäer Reich, behielt aber das Amt des Hohenpriesters der Aphrodite.

Als Zypern 58n.Chr. unter römische Herrschaft kam, galt die Würde des Hohenpriesters der Aphrodite immer noch als angemessene Entschädigung des letzten ptolemäischen Herrschers und Alt-Paphos als eine der drei wichtigsten Städte Zyperns.

Das Heiligtum der Aphrodite zog Reisende und Pilger aus der gesamten römischen Welt an. An Festtagen der Göttin zogen mit Myrthen bekränzte Gläubige in feierlicher Prozession vom Hafen in Neu-Paphos zum Tempel in Alt-Paphos. Sogar der Kaiser Titus besuchte 69n.Chr. auf seinem Weg nach Syrien den Tempel von Paphos.

Die Stadt blühte bis ins 4. Jhd. hinein und ihre Bauten erstreckten sich bis in die Küstenebene. Die Ausbreitung des Christentums führte aber zum Rückgang des Aphrodite Kults und Alt-Paphos versank in der byzantinischen Zeit in der Bedeutungslosigkeit eines Dorfes.

Im 13. Jhd. erbauten die Lusignans am Rande des Stadthügels eine Burg, errichteten Rohrzuckerplantagen und auf dem Hügel eine Rohrzucker-Raffinerie. Die Burg wurde 1426 von den Mamelucken geplündert und teilweise zerstört.

Burg Kouklia

Heute ist das Gelände des Tempels von Gebäuderesten übersät. Die antike Stadt war wesentlich größer als das heutige Dorf Kouklia, das das Zentrum des antikenWohngebietes überdeckt.

Das Heiligtum war nie ein Tempel im klassischen Sinne, sondern ein Kultanlage, mit einem großen offenen Bereich auf dem nur ein verhältnismäßiger kleiner Kultbau stand. Das Kultsymbol der Göttin ist ein Kultstein (ein großer schwarzer kegelförmiger Stein), der an großen Festtagen mit Öl gesalbt und mit Blumen bekränzt wurde.

Die Erinnerung an die alten heidnischen Kulte ist in Kouklia noch heute lebendig. Denn bis heute opfern junge Mütter an einem großen Stein der alten Tempelmauer der Panagia Galatariotissa ( der Milch spendenden Jungfrau) Kerzen; ein Nachklang des uralten Fruchtbarkeitskultes.