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

Ο ναός ανήκει στον τύπο της τρίκλιτης καμαροσκεπούς βασιλικής με νάρθηκα και γυναικωνίτη -το μοναδικό στην Καστοριά-, στον οποίο διαμορφώνεται μικρό παρεκκλήσι, το λεγόμενο «ασκηταριό», αφιερωμένο στην αγία Άννα. Βαρείς πεσσοί χωρίζουν το εσωτερικό σε τρία κλίτη, από τα οποία το κεντρικό υπερυψώνεται έντονα, σχηματίζοντας «τρουλοκαμάρα». Στην τρίπλευρη κόγχη του ιερού βήματος διαμορφώθηκε κτιστό σύνθρονο με επισκοπικό θρόνο. Η τοιχοποιία του ναού απαντάται σε όλα τα βυζαντινά μνημεία της Καστοριάς και αναλύεται σε ισόδομες ζώνες λίθων που περιβάλλονται από πλίνθους και κεραμοπλαστικά «γράμματα» στους κατακόρυφους αρμούς. Ζωφόρος με πήλινα πλακίδια κοσμεί το κεντρικό κλίτος και τα αετώματά του, καθώς και την κόγχη του ιερού βήματος. Στα τέλη του 12ου - αρχές του 13ου αιώνα ο ναός ανακαινίσθηκε και διακοσμήθηκε εκ νέου με τοιχογραφίες, που κάλυψαν το φωταγωγό του κεντρικού κλίτους σεβόμενες την παλαιότερη ιστόρηση. Εκτός από τις ευαγγελικές σκηνές, ιδιαίτερο εικονογραφικό ενδιαφέρον παρουσιάζει η προσωποποίηση των τριών ηλικιών του Χριστού (Εμμανουήλ, Παντοκράτωρ, Παλαιός των Ημερών). Όλα τα έργα τεχνοτροπικά ανήκουν στο ρεύμα της ακαδημαϊκής ζωγραφικής, που έχει τυποποιήσει στοιχεία του 12ου αιώνα, κινούμενη στο πλαίσιο του υστεροκομνήνειου ύφους. Στη διάρκεια του 13ου και του 14ου αιώνα πολλές αφιερωματικές παραστάσεις, που δεν ακολουθούν συγκεκριμένο εικονογραφικό πρόγραμμα, κόσμησαν τα χαμηλότερα μέρη των τοίχων και των πεσσών. Οι παραστάσεις αυτές συνοδεύονται από επιγραφές με αναφορά των ονομάτων των αφιερωτών. Ανάμεσά τους ξεχωρίζει η προσωπογραφία του ιερέα Θεόδωρου Λημνιώτη (τέλη 13ου - αρχές 14ου αιώνα), που προσφέρει ομοίωμα του ναού στον άγιο Στέφανο, ενώ αξιόλογη είναι και η απεικόνιση του «ελαχίστου ικέτη Γεωργίου», του 1338, κάτω από παράσταση της Γοργοεπηκόου. Οι πολλές αφιερωματικές παραστάσεις, η χρήση του ναού για ταφές, η ύπαρξη του συνθρόνου-καθέδρας και του «ασκηταριού», οδηγούν στην υπόθεση ότι ο ναός πιθανόν ήταν μοναστηριακός.

Στις αρχές του 20ού αιώνα οι ανάγκες για μεγαλύτερους χώρους οδήγησαν στην επαύξηση του ναού με την προσθήκη εξωνάρθηκα. Σήμερα, για τη διάσωση και ανάδειξη του μνημείου έχουν εκπονηθεί μελέτες για την αναστήλωση του αρχιτεκτονήματος και τη συντήρηση των τοιχογραφιών.