Στην Παροικία, πρωτεύουσα της Πάρου, σε μικρή απόσταση από το λιμάνι, βρίσκεται ο επιβλητικός ναός της Παναγίας της Εκατονταπυλιανής. Πρόκειται για έναν από τους σπουδαιότερους και καλύτερα διατηρημένους χριστιανικούς ναούς, του Ελλαδικού χώρου.
Σύμφωνα με την παράδοση της Πάρου, ο ναός χτίστηκε στα μέσα του 4ου αι. από την Αγία Ελένη ή από το Μεγάλο Κωνσταντίνο, ο οποίος εκπλήρωσε το τάμα της μητέρας του. Στην ίδια τοποθεσία υπήρχε ένας ναός, πριν από τον 4ο αιώνα.
Σ’ αυτό τον ναό είχε προσκυνήσει η Αγία Ελένη, όταν πέρασε από την Πάρο, πηγαίνοντας στους Αγίους Τόπους για να βρεί τον Τίμιο Σταυρό. Ο θρύλος λέει, ότι η Αγία Ελένη έκανε τάμα στην εικόνα της Παναγίας, πως αν κατάφερνε να βρει τον Τίμιο Σταυρό, θα έχτιζε στη Χάρη της, έναν μεγαλύτερο και λαμπρότερο ναό στην Πάρο. Η Αγία Ελένη πραγματοποίησε το τάμα της, ο ναός όμως, στο μεγαλύτερο μέρος του καταστράφηκε, πιθανότατα από πυρκαγιά και ανακατασκευάστηκε επί Ιουστινιανού, στα μέσα του 6ου αι.
Η ονομασία του Ναού της Εκατονταπυλιανής ή Καταπολιανής, προέρχεται από τον όρο «καταπόλα» και σημαίνει «κατά την πόλη», καθώς πιθανότατα «δείχνει» το σημείο όπου βρισκόταν η αρχαία πόλη της Πάρου. Η σημερινή, επίσημη ονομασία του Ναού είναι Εκατονταπυλιανή, που συνδέεται και αυτή με έναν θρύλο:
«Ενενήντα εννέα φανερές πόρτες έχει η Καταπολιανή. Η 100η είναι κλειστή και δεν φαίνεται. Θα φανεί και θα ανοίξει, όταν οι Έλληνες πάρουν την Πόλη»…
Υπάρχει και ένας άλλος θρύλος, που εμπεριέχει τραγικότητα και συνδέεται με τη μεγάλη Μνημειακή Πύλη, που τοποθέτησε στη βόρεια πτέρυγα του Ιερού Προσκυνήματος, λίγα μέτρα πιο πέρα από το παρεκκλήσι της Αγίας Θεοδοσίας, ο καθηγητής Ορλάνδος, κατά τη διάρκεια της αναπαλαίωσης της Εκατονταπυλιανής.
Οι δύο ανθρώπινες μορφές που βρίσκονται στις κυβοειδής βάσεις που στηρίζουν ένα μαρμάρινο διάκοσμο, εξάπτουν τη λαϊκή φαντασία. Σύμφωνα λοιπόν, με το λαϊκό θρύλο, την Εκατονταπυλιανή επί Ιουστινιανού, έχτισε ο πρώην βοηθός του πρωτομάστορα της Αγιάς Σοφιάς, Ιγνάτιος.
Όταν ο μαθητής ολοκλήρωσε το ναό κάλεσε το δάσκαλο του για να θαυμάσει το έργο του. Ο πρωτομάστορας, ένοιωσε ζήλια και από φόβο μήπως τον ξεπεράσει ο μαθητής του, τον παρέσυρε στην οροφή δήθεν να του δείξει ένα σοβαρό αρχιτεκτονικό του λάθος.
Από εκεί τον έσπρωξε, αλλά πέφτοντας ο μαθητής, στην προσπάθειά του να σωθεί, πιάστηκε από τα ρούχα του Πρωτομάστορα. Το αποτέλεσμα ήταν να βρεθούν και οι δύο στο κενό, να πέσουν και να σκοτωθούν μπροστά στο ναό. Λέγεται λοιπόν, πως οι δύο μορφές αναπαριστούν τον πρωτομάστορα και το μαθητή του.
Στην πραγματικότητα οι δυο μορφές δεν έχουν την παραμικρή σχέση ούτε με την Αγιά Σοφιά ούτε με την Εκατονταπυλιανή, καθώς είναι πολύ παλιότερες. Πρόκειται για δύο σατύρους, που αποσπάστηκαν από κάποιο αρχαίο ιερό του Διονύσου, όπως και τόσα άλλα αρχαιολογικής αξίας αρχαία μέλη.
Ο περίλαμπρος ναός με τις 99 ανοιχτές και τη μία κλειστή πύλη είναι ένα ολόκληρο κτιριακό συγκρότημα, με τον κυρίως ναό και με έξι παρεκκλήσια αφιερωμένα σε αγίους όπως ο Άγιος Φίλιππος, οι Άγιοι Ανάργυροι.
Στον εξωτερικό χώρο οι επισκέπτες έχουν την ευκαιρία να θαυμάσουν, εκτός από την τεράστια σιδερένια πύλη της εισόδου, και τους υπόλοιπους ναούς όπως την περίφημη βασιλική του Αγίου Νικολάου, το ναό της Αγίας Θεοδοσίας αλλά κυρίως το καλοδιατηρημένο βαπτιστήριο του 4ου αι., το αρχαιότερο σε όλη την ορθόδοξη Ανατολή.
Το εσωτερικό της εκκλησίας δεν στερείται τίποτα από την αίγλη του εξωτερικού, αντίθετα αποπνέει το μεγαλείο μιας μακραίωνης παράδοσης, δημιουργώντας αισθήματα χαράς και πνευματικής ανάτασης, ενισχύοντας την πίστη των προσκυνητών.
Κατά την αναπαλαίωση του ναού μεταξύ 1959-1966 ο αρχαιολόγος Αναστάσιος Ορλάνδος αποκάλυψε ένα Γυμνάσιο –γυμναστήριο- της ρωμαϊκής εποχής, με ένα θαυμάσιο δάπεδο με μωσαϊκό, το οποίο κοσμούν οι Άθλοι του Ηρακλή και το οποίο σήμερα έχει μεταφερθεί στην αυλή του Αρχαιολογικού Μουσείου της Πάρου, όπου φιλοξενούνται πάρα πολλά ακόμα κομμάτια, της κλασικής αλλά και της αρχαϊκής εποχής, όταν η Πάρος ευημερούσε, και τα οποία επί αιώνες φυλάσσονταν στα υπόγεια της Εκατονταπυλιανής.