Στο Β.Α τμήμα της πόλης της Πάρου και σε μικρή απόσταση από το λιμάνι δεσπόζει ο ναός της Εκατονταπυλιανής Παναγίας, μνημείο παλαιοχριστιανικό που κτίστηκε πιθανότατα κατά τον 4ο αιώνα μ.Χ. Θρύλοι ανακατεμένοι με αλήθειες θέλουν την Αγία Ελένη να υπόσχεται την ανέγερση ενός μεγάλου ναού στη θέση ενός μικρότερου σε περίπτωση που κατάφερνε να βρει τον Τίμιο Σταυρό στους Άγιους τόπους που πήγαινε
Η προσδοκία της πραγματοποιήθηκε και η Αγία Ελένη εκπλήρωσε το τάμα της ή, κατά άλλους, έβαλε το γιο της Μεγάλο Κωνσταντίνο να το εκπληρώσει. Η αρχικά ξυλόστεγη βασιλική εκκλησία καταστρέφεται πιθανότατα από πυρκαγιά και ο Ιουστινιανός την ανακατασκευάζει προσθέτοντας θόλους και τρούλους. Οι διάφοροι κατακτητές επέφεραν σημαντικές καταστροφές στο μνημείο, ωστόσο ο σεισμός του 1773 αποδείχθηκε πολύ σκληρός μπροστά στο μεγαλείο του και η επισκευή που ακολούθησε αλλοίωσε την αρχική του μορφή.
Σημαντική ανακατασκευή ξεκίνησε το 1959 που έφερε το ναό στη μορφή που είχε κατά την εποχή του Ιουστινιανού. Στο ναό μπορεί ο επισκέπτης να απολαύσει γλυπτά που προέρχονται από το ναό της Δήμητρας καθώς και το αρχαιότερο και καλύτερα διατηρημένο βαπτιστήριο. Επίσης στο ναό στεγάζεται και το Βυζαντινό μουσείο της Παροικιάς με σπάνια θρησκευτικά κειμήλια