La Panaghia Katapoliani est ceinte d'un mur haut de huit mètres cinquante et long de 252 mètres. La cour intérieure où se trouve la basilique fait approximativement quarante-deux mètres de long sur trente-quatre mètres de large. Trois des côtés du rectangle sont en fait composés de bâtiments, abritant des cellules de moines, sur deux étages, dont une partie ont été transformées en boutique pour les pèlerins, en musée byzantin et en bureaux pour l'évêché. Les murs furent construits en deux temps : d'abord la muraille elle-même, à l'époque du duché de Naxos afin de protéger le sanctuaire des attaques de pirates, puis, au XVIIe siècle, les cellules des moines. La majeure partie de la cour est aménagée en jardin et abrite des tombes, dont celle de Manto Mavrogenous.
De nombreux (plus de 2 500) fragments d'architecture et de sculpture antiques ont été remployés pour les constructions de la basilique. Dans l'église principale : les pilastres de marbre qui encadrent le portail proviennent d'un autel classique décoré de triglyphes dédié à Zeus Eleutherios (l'inscription ZEYΣ EΛEYΘEPIOΣ est encore visible sur le linteau du portail) ; les arches des colonnades qui séparent les nefs proviennent des temples archaïques du kastro ; les architraves et les bases des colonnes ont été empruntées à un temple hellénistique ; à droite de l'iconostase les pierres viennent d'un temple à Sérapis, comme le prouve l'inscription APXONTOΣ XAPH ΣEPAΠH. Les colonnes et architraves de la chapelle Saint-Nicolas sont issues d'un temple dorique de la fin de l'époque archaïque.
Cette chapelle au nord-est de la basilique est la partie la plus ancienne de l'ensemble architectural (et de l'île de Paros en général). Elle est datée de 313-326. Elle a une forme rectangulaire (19 mètres sur 15 mètres), divisée en trois nefs séparées par des colonnes antiques de type dorique remployées. La nef centrale est la plus large. À l'origine, elle était couverte d'un toit à deux pentes en bois, dans le style de la basilique paléochrétienne typique. À l'époque de Justinien, le toit fut remplacé par un dôme central et une demi coupole au-dessus de l'autel, l'ensemble en calcaire vert-jaune, lui donnant ainsi l'apparence d'une église en croix grecque inscrite. Le résultat est une combinaison exceptionnelle : une basilique avec un dôme. L'église fut d'abord dédiée à la Dormition de la Vierge. La chapelle actuelle est dédiée à Saint Nicolas, peut-être depuis que l'église principale est elle-même dédiée à la Vierge. L'iconostase en marbre pourrait remonter au XVe siècle, avec des parties plus anciennes. Trois icônes s'y trouvent : une Vierge Éléousa attribuée à Dimitrios, au XVIIIe siècle ; un Christ Pantocrator du XVIIe siècle ; un Saint Nicolas de facture récente. Derrière l'iconostase, le petit synthronon de cinq gradins rappelle que l'évêque de Paronaxia siège aussi (et ce dès l'origine) sur Paros.
Dans la conque de l'abside on peut voir une fresque datant de 1736 représentant le Christ et les Apôtres. Cependant, la fresque la plus importante de cette chapelle Saint-Nicolas est sur le mur nord. C'est la fresque la plus ancienne de toute la basilique : elle remonte au VIIe ou VIIIe siècle et représente Élisabeth la mère de Jean le Baptiste dans le style d'une « Vierge à l'enfant ».
Le baptistère se trouve au sud de l'église principale. Il mesure 16,50 mètres sur 15 mètres. Il est relié par un narthex à l'église principale. Il est considéré comme le plus ancien et le mieux préservé des baptistères de l'Orient orthodoxe. Sa construction remonte au IVe siècle. C'était alors une basilique paléochrétienne à trois nefs avec un toit en bois. Comme pour la chapelle Saint-Nicolas, il fut remanié au VIe siècle : son toit fut remplacé par un dômes et des coupoles en calcaire coloré. Au centre, sous le dôme, se trouvent les fonds baptismaux (le Photistirion), ils remontent eux aussi au IVe siècle lorsqu'on baptisait encore des adultes par immersion totale.
Sur le pilier nord-est soutenant le dôme, on peut apercevoir (difficilement) un fragment très abîmé de fresque représentant un hiérarque. Sur un mur, dans un aussi mauvais état de conservation, un jeune saint tenant une croix et couronné par un ange a été identifié à un Saint Georges
Les fouilles archéologiques du professeur Orlandos ont mis au jour deux bâtiments antiques superposés sous l'église principale. Le plus ancien, non daté, à un mètre cinquante de profondeur possédait quatre colonnes. Trois ont été à nouveau recouvertes, mais une a été laissée visible dans le sol de l'église actuelle. Au-dessus, à quatre-vingt centimètres de profondeur, se trouvait un gymnase romain, encore utilisé au début du IVe siècle. Une mosaïque représentant les travaux d'Hercule, révélée par les fouilles, a été déplacée dans la cour du musée archéologique.
L'église constantinienne fut construite vers 328-337. C'était une basilique paléochrétienne cruciforme, avec un toit en bois et une tour avec un dôme à la croisée du transept. Au centre se trouvait un ambo (pupitre surélevé). L'église était précédée vers l'ouest d'un atrium avec au centre une « phiale » pour l'eau bénite. Cet atrium, inclus dans la structure, faisait que l'église constantinienne était plus longue (56 mètres) que le bâtiment actuel.
L'église actuelle (inscrite dans un rectangle de 40 m sur 25 m), construite à l'époque de Justinien, date donc du VIe siècle. Elle combine elle aussi les aspects de basilique cruciforme à dôme avec ceux d'église à plan centré avec dôme. La croisée du transept est surmontée d'une coupole soutenue par quatre piliers. Les nefs latérales font toutes la largeur du bâtiment, transept inclus. Ces nefs latérales sont séparées de la nef centrale par une colonnade. Tout autour de la nef centrale et des bras du transept court, au-dessus de la colonnade, le gynécée : la galerie des femmes qui date du moment où hommes et femmes étaient encore séparés lors des messes. L'église est précédée d'un portique percé de trois portes, une par nef, le portail central pour la nef centrale étant le plus grand.
Le long du mur de la nef nord se trouve une petite chapelle dédiée à Sainte Théoctiste, installée au-dessus de la tombe de celle-ci. Derrière l'iconostase peuvent s'apercevoir le synthrônon (amphithéâtre capitulaire) et le ciborium couvrant l'autel principal. Le ciborium, daté du VIe siècle est un des plans anciens connus. Il incorpore quatre colonnes antiques remployées. Sous l'autel coule une source à laquelle buvait Sainte Théoctiste selon la légende.
Peu de fresques (remontant toutes au XVIIe ou XVIIIe siècle) sont encore visibles dans l'église principale. Elles datent d'avant la reféction du XVIIIe siècle. Elles ont alors été martelées pour créer des creux où le plâtre puis l'enduit de chaulage pouvaient mieux adhérer. Elles ont donc été fortement abîmées avant d'être longtemps cachées. Les travaux de restauration du Professeur Orlandos les ont fait réapparaître, mais en fort mauvais état. Quelques scènes tirées de l'Ancien Testament peuvent encore difficilement s'apercevoir çà et là. Dans une conque sur la droite du narthex, on peut voir une « Vierge Nikopoios » (de Victoire), avec le Christ en médaillon sur la poitrine, flanquée des archanges Michel et Gabriel. Sur les quatre pendentifs de la coupole centrale sont représentés des séraphins. Sur le mur nord peut se voir une « Vierge Hodegetria ». Les fresques les mieux conservées sont celles représentant les vingt-quatre oikoi (couplets) de l'hymne Akathistos.
L'iconostase présente diverses icônes du XVIIe siècle recouvertes d'argent en 1788 qui ont été offertes lors de la restauration par Nikólaos Mavrogénis : un Christ entouré de vignettes évoquant le Dodékaorton (les douze fêtes orthodoxes principales) et surmonté d'un Dieu le père au milieu des anges et des séraphins ; une Vierge dite « Ekatontapyliani », réputée miraculeuse. Au dessus de la porte de l'iconostase se trouve une Trinité entourée de la Vierge, Saint Jean Baptiste et d'anges datant de 1759. Sur la porte elle-même, l'archange Saint Michel remonte à 1666. Il est surmonté d'un Ecce Homo. D'autres icônes sont visibles ailleurs dans l'église : un Christ en grand prêtre (1759) fut ajouté sur le siège épiscopal daté de 1853 ; une « Vierge de la Passion » dite aussi « Vierge du vendredi » et par assimilation « Aghia Paraskévi » datant du XVIe siècle au pied d'une colonne sud-ouest ; une Vierge orante au pied d'une colonne nord-ouest qui s'est révélée ancienne (XIIe siècle) suite à une restauration qui a enlevée son revêtement d'argent ; une Trinité et une consécration de Jacques le majeur le long du mur nord (XVIIIe siècle).