Ο Παλαιολόγειος ναός της Αγίας Αικατερίνης βρίσκεται στο βορειοδυτικό άκρο της Άνω Πόλης. Το κτίσμα χρονολογείται από τους ερευνητές στα τέλη του 13ου και αρχές 14ου αιώνος. Ο ρυθμός του ναού είναι σύνθετος τετρακιόνιος σταυροειδής εγγεγραμμένος, με πέντε τρούλους και κλειστή περιμετρική στοά που καταλήγει στα ανατολικά σε πρόθεση και διακονικό (ο σημερινό παρρεκλήσιο της Αγίας Ευφημίας. Στα χρόνια του Σουλτάνου Βαγιαζίτ του Β΄(1481-1512), ο ναός μετατράπηκε σε τζαμί (Yakup Pasa Camii).
Στην κόγχη του ιερού βήματος σώζονται μορφές ιεραρχών που λειτουργούν και η κοινωνία των αγίων αποστόλων. Επίσης στον τρούλο σώζονται προφήτες και άγγελοι, γύρω από τον κατεστραμμένο Παντοκράτορα. Στον βορειοδυτικό τρούλο υπάρχει ο Χριστός Εμμανουήλ.
Στον κυρίως ναό σώζονται παραστάσεις από τα θαύματα του Κυρίου (γάμος της Κανά, θεραπεία παραλύτου, ίαση του τυφλού, ίαση του λεπρού, ο Χριστός που ησυχάζει τα νερά της λίμνης και ο διάλογος του Χριστού με τη Σαμαρείτιδα. Στο δυτικό σκέλος του περιστώου σώζονται σπαραγματικές μορφές αγίων κυρίων ασκητών και στηλιτών. Λόγω των εκτενών παραστάσεων από τη ζωή του Χριστού ο ναός ταυτίστηκε από τους μελετητές με το καθολικό της μονής Παντοδυνάμου. Η τοιχογράφηση του ναού τοποθετείται στα 1315 (αλαιολόγεια περίοδος), εποχή πλούσιας καλλιτεχνικής παραγωγής. Μετά την απελευθέρωση της Θεσσαλονίκης το 1912 ο ναός αφιερώθηκε στην Αγία Αικατερίνη.