Στο βορειοδυτικό άκρο της κάτω πόλης, εντός του οχυρωματικού περιβόλου, βρίσκεται ο επισκοπικός ναός της πόλης, γνωστός και με ονομασίες «βασιλική των Κατηχουμένων» ή «Σαράντα Πόρτες». Η παράδοση θέλει τον συγκεκριμένο ναό να τιμάται στο όνομα του Αγίου Νικολάου, αν και έχει διατυπωθεί και η άποψη από τον Ανδρέα Ξυγγόπουλο ότι ο ναός ήταν αφιερωμένος στον Άγιο Δημήτριο, λαμβάνοντας υπόψη τη μεγάλη παράσταση του Αγίου Δημητρίου στον νότιο τοίχο του κεντρικού κλίτους του ναού, όπου σώζεται και αφιερωματική επιγραφή του επισκόπου Σερβίων, Μιχαήλ.

Ο ναός αποτελεί ένα τυπικό δείγμα μεσοβυζαντινής τρίκλιτης βασιλικής με νάρθηκα και υπερυψωμένο κεντρικό κλίτος με φωταγωγό. Το κεντρικό κλίτος του ναού στεγαζόταν με αμφικλινή στέγη, ενώ τα πλάγια κλίτη και ο νάρθηκας έφεραν ξεχωριστή μονόριχτη στέγαση. Τα κλίτη χωρίζονται μεταξύ τους με τοίχους, που φέρουν το καθένα από τέσσερα τοξωτά ανοίγματα. Το μεσαίο κλίτος είναι διπλάσιο σε πλάτος από τα πλάγια κλίτη και συγκοινωνεί με το νάρθηκα μέσω τρίβηλου ανοίγματος, από το οποίο διατηρούνται μόνο οι βάσεις των κιόνων. Η μεγάλη ημικυλινδρική αψίδα στα ανατολικά του ναού έχει σήμερα καταρρεύσει, η στιβαρή κατασκευή της όμως απέτρεψε την πλήρη καταστροφή της κι έτσι σήμερα μπορούμε να έχουμε μια σαφή εικόνα της μορφής της, που είναι ημικυλινδρική με αβαθή τυφλά τόξα και ένα παράθυρο.

Ο ναός χρονολογείται γύρω στις αρχές του 11^ου αιώνα αλλά δέχτηκε διαδοχικές φάσεις μετασκευών από τον 12ο έως και τον 16ο αιώνα, με πιο χαρακτηριστική την μετασκευή του 14ου αιώνα κατά την οποία το νότιο κλίτος μετατρέπεται σε στοά.

Για τον γλυπτό διάκοσμο του ναού δεν μπορούν να εξαχθούν ασφαλή  συμπεράσματα από τα λιγοστά δείγματα που έχουν σωθεί. Τα δύο τμήματα μαρμάρινου επιστυλίου, που εντοιχίστηκαν στον ναό σε δεύτερη χρήση, προέρχονται πιθανότατα από το μαρμάρινο τέμπλο του ναού και φέρουν απλή διακόσμηση με πτηνά να ραμφίζουν σταφύλια σε έναν ελισσόμενο βλαστό. Η αδρή κατεργασία του αναγλύφου έχει οδηγήσει ήδη τον Ανδρέα Ξυγγόπουλο να χρονολογήσει τα γλυπτά στις αρχές του 11^ου αιώνα δηλώνοντας ότι πρόκειται για «επαρχιακήν αδέξιαν απομίμησιν καλού πρωτοτύπου».

Η βασιλική φέρει ενδιαφέροντα τοιχογραφικό διάκοσμο σε δύο τουλάχιστον επάλληλα στρώματα. Το πρώτο, που ήταν σύγχρονο με την ανέγερση του ναού, καλύπτεται από το δεύτερο που χρονολογείται στον 13ο αιώνα και είναι ορατό, σήμερα, σε αποσπασματική κατάσταση. Η κατάσταση των τοιχογραφιών είναι καλύτερη στο μεσαίο κλίτος του ναού, καθώς στα πλάγια κλίτη και τον νάρθηκα η ζωγραφική έχει καταστραφεί σχεδόν ολοκληρωτικά λόγω της έκθεσης επί μακρόν στις καιρικές συνθήκες. Στο μεσαίο κλίτος η διάταξη των τοιχογραφιών γίνεται σε τρεις ζώνες: η ανώτερη ζώνη, που είναι σήμερα εντελώς δυσδιάκριτη, έφερε δέκα διάχωρα με παραστάσεις, πιθανότατα Δωδεκαόρτου, ενώ από τη μεσαία ζώνη μπορούμε ακόμα σήμερα να διακρίνουμε, αν και με αρκετή δυσκολία, σκηνές από τα Πάθη του Χριστού και τα Εισόδια της Θεοτόκου. Η κατώτερη ζώνη είναι η αυτή που σώζεται σε καλύτερη κατάσταση και περιλαμβάνει ολόσωμους ιεράρχες, στρατιωτικούς και μοναχούς αγίους και γυναίκες αγίες. Ξεχωρίζουν, αν και σε αποσπασματική κατάσταση διατήρησης, οι παραστάσεις του εναγκαλισμού των Αγίων Πέτρου και Παύλου και η παράσταση του μετωπικού ολόσωμου Αγίου Δημητρίου με τις μορφές του ευλογούντα Ιησού και ενός αγγέλου που του παραδίδει σπαθί, οι οποίες αποδίδονται σε μικρότερη κλίμακα.