Ο ναός βρίσκεται στην ανατολική πλευρά της πόλης, στους πρόποδες του βουνού του Αγίου Αθανασίου. Είναι τρίκλιτη θολοσκέπαστη βασιλική με νάρθηκα. Τα κλίτη καλύπτονται από ημικυλινδρικούς θόλους εκ των οποίων ο μεσαίος είναι αισθητά υπερυψωμένος. Εσωτερικά, οι τοίχοι των κλιτών διατρυπώνται από τοξωτά ανοίγματα. Στον νάρθηκα, όπου σχηματίζεται και όροφος, η κάλυψη γίνεται με θόλο μορφής τέταρτου κύκλου. Ο όροφος είναι το αποκαλούμενο "ασκητάριο", το οποίο είναι αφιερωμένο στην Αγία Άννα. Στην ανατολική πλευρά, διατηρείται στο ιερό το σύνθρονο, σημάδι που τονίζει τη σημαντικότητα του μνημείου, όπως και τον αρχαϊκό του χαρακτήρα. Εξωτερικά, οι όψεις του διακοσμούνται με τον γνωστό τρόπο της εναλλαγής σε διάφορα σχήματα του γκριζωπού ακανόνιστου ασβεστόλιθου και των κεραμικών πλακών. Επιπλέον διακοσμητικά στοιχεία εμφανίζονται εδώ οι χαραγμένοι κεραμικοί πλίνθοι σε σχήμα Χ, που δημιουργούν μια ζωφόρο πάνω από τα παράθυρα απ' όλες τις πλευρές του υπερυψωμένου ορθογώνιου φωταγωγού. Η ανατολική όψη του κεντρικού κλίτους έχει και δύο ήλιους σχηματισμένους από βήσαλα (κεραμικές πλάκες).

Όλα τα παράθυρα του Αγίου Στεφάνου είναι μονόλοβα και διαφορετικά μεταξύ τους, χωρίς να διαταράσσουν την ισορροπία στα ανοίγματα. Διαφέρει το μέγεθος και το άνοιγμα των τόξων. Η διακόσμηση των παραθύρων γίνεται με οδοντωτές ταινίες.Ένα ιδιαίτερο χαρακτηριστικό του ναού σε σχέση με τα άλλα μεγάλα μνημεία της πόλης, είναι η ημιεξαγωνική αψίδα του ιερού.Εσωτερικά, ο ναός είναι διακοσμημένος με τοιχογραφίες, που προέρχονται από διαφορετικές εποχές. Από τον 9ο αιώνα μέχρι και τον 15ο αιώνα. Ξεχωρίζουν οι τοιχογραφίες της πρώτης φάσης (τέλη 9ου αιώνα), κυρίως για τις πολύτιμες πληροφορίες που μεταφέρουν για την τέχνη της μεταεικονομαχικής περιόδου.