Στο ύψωμα ανάμεσα στις δύο παραδοσιακές συνοικίες της Καστοριάς με τα αρχοντικά σπίτια, το Απόζαρι και το Ντολτσό, δεσπόζει ένα από τα παλαιότερα εκκλησιαστικά μνημεία των Βαλκανίων, ο βυζαντινός ναός του Αγίου Στεφάνου.
Πρόκειται για μικρή, τρίκλιτη, θολοσκέπαστη βασιλική, που φαίνεται ότι κτίστηκε γύρω στα μέσα του 9ου αιώνα. Τα κλίτη της χωρίζονται με πεσσούς (τετράγωνης διατομής κίονες) και καλύπτονται με ημικυλινδρικές καμάρες. Το μεσαίο είναι ιδιαίτερα υπερυψωμένο και έχει παράθυρα, σαν φωταγωγός, στοιχείο που χαρακτηρίζει τις μεσοβυζαντινές βασιλικές της Καστοριάς. Στα ανατολικά, στην κόγχη, σώζεται υποτυπώδες σύνθρονο με τον θρόνο του επισκόπου, το μοναδικό στην Καστοριά. Στα δυτικά υπάρχει διώροφος νάρθηκας, με κλίμακα που οδηγεί στον δεύτερο όροφο, στον γυναικωνίτη, μέσα στον οποίο διαμορφώνεται μικρό παρεκκλήσιο της Αγίας Άννας, το λεγόμενο ασκηταριό, στοιχείο που επίσης συναντάται μόνο στον ναό αυτό. Η στοά στη βόρεια και δυτική πλευρά του κτηρίου είναι προσθήκη του 20ού αιώνα.
Η τοιχοποιία του ναού είναι η χαρακτηριστική των μνημείων της Καστοριάς. Αποτελείται από πέτρες στο φυσικό τους σχήμα ή αδρά πελεκημένες, που περιβάλλονται από κονίαμα, πλαισιώνονται με πλίνθους οριζόντια ή κάθετα, και εναλλάσσονται με συνθέσεις πλίνθων που σχηματίζουν διακοσμητικά γράμματα ή γεωμετρικά σχήματα.
Ο ναός είναι διακοσμημένος με τοιχογραφίες που διακρίνονται σε τρεις διαφορετικές περιόδους. Στην πρώτη, που χρονολογείται στα τέλη του 9ου - αρχές του 10ου αιώνα, ανήκουν οι τοιχογραφίες στο ισόγειο του ναού και του νάρθηκα, καθώς και σε ορισμένα τμήματα του γυναικωνίτη. Ξεχωριστή θέση ανάμεσά τους καταλαμβάνουν οι σκηνές της Δευτέρας Παρουσίας στον νάρθηκα. Από τη δεύτερη περίοδο διατηρούνται κυρίως οι τοιχογραφίες στον ψηλό φωταγωγό, οι οποίες σύμφωνα με την τεχνοτροπία τους θα μπορούσαν να χρονολογηθούν στα τέλη του 12ου αιώνα και στις αρχές του 13ου αιώνα. Στην τρίτη περίοδο (τέλη του 13ου –αρχές 14ου αιώνα) εντάσσονται οι πολυάριθμες αναθηματικές τοιχογραφημένες εικόνες, που αποτελούν ιδιαίτερο χαρακτηριστικό του ναού. Από αυτές ξεχωρίζει η προσωπογραφία στον νάρθηκα του ιερέα Θεόδωρου Λημνιώτη που προσφέρει ομοίωμα του ναού στον άγιο Στέφανο.