Τα στενά δρομάκια επάνω από την οδό Ολυμπιάδος και κοντά στα βορειοδυτικά τείχη κοσμεί ο κομψός ναός της Αγίας Αικατερίνης. Το αρχικό όνομα και η χρονολογία ίδρυσης του ναού μας είναι άγνωστα. Τα γνωρίσματα της αρχιτεκτονικής και της ζωγραφικής του παραπέμπουν στα τέλη του 13ου με αρχές του 14ου αιώνα, ενώ ειδική επιστημονική έρευνα (δενδροχρονολόγηση) υπέδειξε τα χρόνια πριν από το 1310.
Ο ναός είναι σύνθετος τετρακιόνιος σταυροειδής εγγεγραμμένος πεντάτρουλος, με περίστωο και δύο παρεκκλήσια στο ανατολικό πέρας των πλαγίων στοών, τύπος που γνώρισε ιδιαίτερη διάδοση στην παλαιολόγεια Θεσσαλονίκη. Η μορφολογία του κτίσματος με το επιμελημένο πλινθοπερίκλειστο σύστημα δόμησης, τον κεραμοπλαστικό διάκοσμο, τους πλίνθινους ημικίονες και τις κόγχες στους τρούλους, τα βαθμιδωτά τόξα και τα αψιδώματα στα παράθυρα και τα μεγάλα δίβηλα και τρίβηλα ανοίγματα στις τρεις όψεις συγκαταλέγουν το μνημείο ανάμεσα στα σημαντικότερα παραδείγματα της μακεδονικής αρχιτεκτονικής της παλαιολόγειας αναγέννησης. Ενσωματωμένα εφυαλωμένα πλακίδια και μαρμάρινα μέλη από αρχαιότερα μνημεία ποικίλλουν τις όψεις.
Κατά τις αναστηλωτικές εργασίες στα 1947-1951 αποκαλύφθηκε ο αποσπασματικά σωζόμενος τοιχογραφικός διά¬κοσμος του ναού, ο οποίος πραγματοποιήθηκε σε μία φάση (τέλη 13ου- αρχές 14ου αιώνα). Στο ιερό βήμα σώζονται οι συλλειτουργούντες ιεράρχες και η Κοινωνία των Αποστόλων, στον κυρίως ναό αποσπασματικά θέματα από το Βίο του Ιησού, στον τρούλο άγγελοι και προφήτες, ενώ στο νάρθηκα μορφές αγίων ασκητών. Από την επιλογή των θεμάτων διατυπώθηκε η υπόθεση ότι ο ναός ήταν μοναστηριακός και αφιερωμένος στη λατρεία του Χριστού. Η ογκηρή τεχνοτροπία των στιβαρών μορ¬φών, τα εκφραστικά πρόσωπα και η πλούσια χρωματική παλέ¬τα συνιστούν γνωρίσματα των καλλιτεχνικών κύκλων της Θεσσαλονίκης των πρώτων δεκαετιών της παλαιολόγειας αναγέννησης και πιθανόν των Μιχαήλ Αστραπά και του Ευτυχίου.
Μετά την άλωση της Θεσσαλονίκης ο ναός μετατράπηκε σε τζαμί με την επωνυμία «Γιακούμπ πασά τζαμί» και οι τοιχογραφίες καλύφθηκαν με επιχρίσματα.
Μετά τους σεισμούς του 1973 πραγματοποιήθηκαν εργασίες στερέωσης του μνημείου.
