Η βασιλική των Κατηχουμένων βρίσκεται στη βορειοδυτική γωνία της κάτω πόλης του κάστρου των Σερβίων και αποτελούσε τον επισκοπικό της ναό. Χρονολογείται γύρω στο 1000, αλλά δέχθηκε μετασκευές σε διάφορες φάσεις από το 12ο έως το 16ο αιώνα.

Η βασιλική είναι τρίκλιτη με νάρθηκα και υπερυψωμένο κεντρικό κλίτος με φωταγωγό. Τα κλίτη χωρίζονται με τοίχους που διατρυπούνται από τέσσερα τοξωτά ανοίγματα. Στην πρώτη οικοδομική φάση το κεντρικό κλίτος στεγαζόταν με ξύλινη αμφικλινή στέγη και τα πλαϊνά με μονόρριχτη, ενώ το κεντρικό κλίτος επικοινωνούσε με τα πλαϊνά μέσω τριβήλου. Το μνημείο διασώζει τοιχογραφικό διάκοσμο σε τρία στρώματα. Το πρώτο είναι σύγχρονο με την πρώτη φάση του ναού, το δεύτερο χρονολογείται στο 13ο αιώνα, επί επισκόπου Μιχαήλ, ενώ το τρίτο, σπαράγματα του οποίου αποκαλύφθηκαν κατά τις τελευταίες ανασκαφικές έρευνες, μπορεί να τοποθετηθεί στο 15ο-16ο αιώνα. Ιδιαίτερο ενδιαφέρον παρουσιάζουν, μεταξύ άλλων, τα σπαράγματα τοιχογραφιών που ανευρέθηκαν στο νότιο κλίτος, στο οποίο κατά την πρώιμη μεταβυζαντινή περίοδο λειτουργούσε παρεκκλήσι. Πρόκειται για τη μορφή Ένθρονου Χριστού Παντοκράτορα, τα χέρια μιας δεόμενης μορφής και τμήμα της μορφής του αγίου Δημητρίου, που συναποτελούν πιθανότατα παράσταση Δέησης. Οι τοιχογραφίες αυτές, σε συνδυασμό και με άλλα στοιχεία, όπως τα τμήματα δαπέδου στα δύο πλάγια κλίτη και το τρίτο στρώμα τοιχογραφιών που σώζεται στο βόρειο και νότιο κλίτος, πιστοποιούν τη λειτουργία της βασιλικής, στα πλάγια κλίτη τουλάχιστον, έως το 16ο-17ο αιώνα.

Ο ναός σήμερα σώζεται σε ερειπιώδη μορφή. Στο πλαίσιο εκπόνησης της μελέτης αποκατάστασής του, κατά τα έτη 1995-2000 πραγματοποιήθηκαν στερεωτικές εργασίες, σωστικές εργασίες συντήρησης των τοιχογραφιών καθώς και ανασκαφές, που έφεραν στο φως πολύτιμα στοιχεία για την ιστορία του μνημείου.