Paphos était une ville située dans le sud-ouest de Chypre. Elle était, au départ, une colonie phénicienne appelée « Vieux Paphos ». Plus tard, une colonie grecque nommée « Nouveau Paphos » a été construite à environ 15 km de la ville d'origine. Nouveau Paphos est devenu le principal centre administratif lorsque Chypre a été rajoutée à l'Empire romain en l'an 22 av. J.‑C.
La ville combinée était célèbre pour son temple. Les habitants ont d'abord dédié le temple à la déesse syrienne Astarté. Selon l'historien romain Tacite, les gens adoraient Astarté à travers d'anciennes cérémonies phéniciennes. Ces cérémonies comprenaient l'application d'huile sur une pierre en forme de cône (possiblement une météorite). Les Grecs ont ensuite identifié Astarté avec leur déesse Aphrodite. Ils croyaient qu'Aphrodite était sortie de la mer.
À Paphos, l'apôtre Paul a rencontré pour la première fois une forte opposition à la Bonne Nouvelle concernant Jésus. Cette opposition est venue d'un homme nommé Élymas. En réponse, Paul a accompli son premier miracle consigné dans la Bible. Paul a rendu Élymas aveugle, mais sa cécité n'était que temporaire, montrant ainsi la miséricorde de Paul (Ac 13.11).