Początki cypryjskiego Nea Pafos sięgają okresu hellenistycznego, a jego pierwsze kamienne budowle powstały w IV wieku p.n.e. Badacze przyjmują że założycielem miasta mógł być król Pafos – Nikokles, bądź egipski władca – Ptolemeusz I, pod którego panowaniem znajdowały się tereny Cypru.
W okresie rzymskim Pafos pełniło funkcję prowincji. Miasto tę funkcję straciło po trzęsieniu ziemi, jakie nawiedziło te tereny w IV wieku n.e , wtedy to stolicę przeniesiono do Salaminy. Jak przekazują „Dzieje Apostolskie” w Pafos odbyło się biczowanie św. Pawła, co było przyczynkiem do ściągania w te tereny wielu pielgrzymów. Samo Pafos stało się ośrodkiem kultu chrześcijańskiego, gdzie wybudowano szereg kościołów i bazylikę.
Dla polskiego czytelnika znamienny będzie fakt, że Pafos było terenem gdzie przez szereg lat, wykopaliska prowadziła Polska Misja Archeologiczna. Prace zostały zapoczątkowane przez prof. Kazimierza Michałowskiego w 1965 roku; następnie kierownikiem wykopalisk od 1966 do 2008 był Andrzej Daszewski, któremu nadano tytuł honorowego obywatela Pafos w podziękowaniu za zasługi dla Pafos.
Najstarszym obiektem odkrytym przez polskich archeologów był tzw. Dom Hellenistyczny. Budynek w którym zachowały się fragmentaryczne dekoracje, posiadał dwa dziedzińce kolumnowe i wielką salę recepcyjną. Na głównym dziedzińcu odkryto datowaną na I wiek p.n.e mozaikę o wymiarach 11,43 x 6,55m, która jest największą mozaiką pochodzącą z tego okresu znalezioną na Cyprze.
Dom Hellenistyczny uległ zniszczeniu podczas trzęsienia ziemi w 126 roku n.e. Prawdopodobnie to spowodowało, że część tej budowli przekształcono i rozbudowano w okresie rzymskim w monumentalną willę o charakterze pałacowym, przeznaczoną dla prokonsula bądź gubernatora wyspy. Podczas wykopalisk w południowo-wschodniej części domu, natrafiono na mozaikę pochodzącą z III wieku n.e, przedstawiającą mitycznego herosa Tezeusza zabijającego w labiryncie Minotaura, którego wizerunek został całkowicie zniszczony. Zmagania obserwuje Ariadna i postacie uosabiające Kretę. Dookoła centralnej części biegnie złożony labirynt. Od przedstawienia mozaiki budynek nazwano Willą Tezeusza.
Willa Tezeusza pełniła dwie funkcje: publiczną i prywatną. Każda z dwóch części posiadała ogród który zdobiły liczne posągi przedstawiające grecko-rzymskich bogów. Nietypowym przedstawieniem jest posąg Afrodyty z mieczem, które odnosi się do specyficznych cypryjskich wierzeń sięgających jeszcze epoki brązu. Afrodytę zaopatrzoną we włócznię przedstawiono również na mozaice.
Południowe skrzydło willi posiadało liczne pomieszczenia reprezentacyjne, którego sciany i podłogi były pokryte freskami i importowanym marmurem. Niestety zachowały się one dość fragmentarycznie, a ich wysokośc miejscami wynosi niecałe 1,50 metra. Posadzki pomieszczeń pokryte były bogatymi mozaikami z V wieku n.e. Najlepiej zachowana przedstawia kąpiel Achillesa w wodach Styksu.
Obok Willi Tezeusza natrafiono na inny budynek nazwany Domem Aiona, w którym odkryto imponującą mozaikę o skomplikowanym znaczeniu ikonograficznym. Pochodzi ona z połowy IV wieku n.e i stanowi wyjątkowe dzieło sztuki rzymskiej.
Dekoracja sali biesiadnej odnosiła się do kultu Dionizosa i Apollina, powiązanego z filozoficzną refleksją nad jednostką i jej życiem.
Ciekawym w tym budynku, jest to że do sali biesiadnej (triclinium) którą zdobiła owa mozaika, wchodziło się bezpośrednio z ulicy. Układ pomieszczeń jak i sceny jakie zdobiły ściany i posadzki sugeruje, że była to siedziba pogańskiego stowarzyszenia, którego wyznawcy wierzyli że zbawienie można osiągnąć również będąc poganinem. Takie rozumowanie różniło się od tradycyjnie wyznawanego kultu.
Dokładne datowanie mozaiki jest możliwe dzięki znalezieniu w jej podkładzie monety Licyniusza z 323 roku n.e. Mozaika częściowo uległa zniszczeniu podczas trzęsienia ziemi, ale została naprawiona w V wieku n.e
