Ο ναός των Αγίων Αποστόλων ιδρύθηκε από τον Πατριάρχη Νήφωνα Α΄(1310-1314) ως καθολικό μονής, αφιερωμένης πιθανόν στην Παναγία. Από το αρχικό συγκρότημα, που είχε ιδρυθεί δίπλα στη Ληταία Πύλη στα ανατολικά τείχη, σώζονται σήμερα μόνο ο ναός, μέρος του πυλώνα και η κινστέρνα, ενώ ανασκαφικά εντοπίστηκαν οι υποδομές προσκτισμάτων της μονής.
Ο ναός ακολουθεί τον τύπο του σύνθετου σταυροειδούς εγγεγραμμένου με τρούλο και περίστωο. Ανατολικά του κυρίως ναού αναπτύσσεται τριμερές ιερό ενώ τις υπόλοιπες τρεις πλευρές περιβάλλει το περίστωο, με τέσσερις τρουλίσκους στις γωνίες, χαμηλότερους από τον κεντρικό. Δυτικότερα, εξωτερικά του αντίστοιχου σκέλους του περιστώου, αναπτύσσεται εξωνάρθηκας, με την κτητορική επιγραφή και τα μονογράμματα του Νήφωνα στα τύμπανα των ανοιγμάτων. Τόσο ο εξωνάρθηκας όσο και το νότιο σκέλος του περιστώου φαίνεται πως αρχικά ήταν ανοιχτά στις όψεις. Το ναό χαρακτηρίζει πλούσιος κεραμοπλαστικός διάκοσμος, ιδιαίτερα στην ανατολική όψη, με συνεχόμενα γεωμετρικά θέματα. Στο ανατολικό άκρο του βορείου σκέλους του περιστώου διαμορφώνεται παρεκκλήσι αφιερωμένο στον Ιωάννη Πρόδρομο. Στην αντίστοιχη θέση στα νότια υπήρχε σκευοφυλάκιο, προσβάσιμο μόνο από το διακονικό.
Ο διάκοσμος του ναού έγινε σε δύο φάσεις. Τα ψηφιδωτά, που καλύπτουν τα θολωτά μέρη του κυρίως ναού, ως τον μαρμάρινο κοσμήτη, αποδίδονται στον Νήφωνα. Οι τοιχογραφίες, που καλύπτουν τους τοίχους του κυρίως ναού και του ιερού καθώς και ολόκληρο το περίστωο και τον εξωνάρθηκα, αποδίδονται στον μαθητή και συνεχιστή του έργου του Παύλο. Η αψίδα του ιερού μοιάζει να έμεινε ακόσμητη. Πιθανόν οι εργασίες να διακόπηκαν μετά την καθαίρεση του Νήφωνα, ενώ και ο Παύλος δεν πρόλαβε να την ολοκληρώσει.
Στον κεντρικό τρούλο σώζεται το κάτω μέρος της μορφή του Παντοκράτορα, που κρατά ευαγγέλιο και ευλογεί, ενώ γύρω του στέκουν δέκα προφήτες, που κρατούν ανοιχτά ειλητάρια με αποσπάσματα από τα έργα τους. Στη βάση του τρούλου, στα ανατολικά, εικονίστηκε το Άγιο Μανδήλιο, ενώ στα σφαιρικά τρίγωνα οι τέσσερις Ευαγγελιστές. Στις καμάρες που φέρουν τον τρούλο αναπτύχθηκαν παραστάσεις από το Δωδεκάορτο: η Γέννηση και η Βάπτιση στη νότια καμάρα, η Μεταμόρφωση και η Βαϊοφόρος στη δυτική, η Σταύρωση και η Ανάσταση στη βόρεια. Στον δυτικό τοίχο, πάνω από την είσοδο προς τον νάρθηκα, εικονίστηκε η Κοίμηση της Θεοτόκου.
Στα χαμηλά μέρη των τοίχων, κάτω από τον κοσμήτη, εικονίστηκαν ιεράρχες και άγιοι. Στα ψηλότερα μέρη των τοίχων, στο περίστωο και τον εξωνάρθηκα, αναπτύχθηκε κύκλος παραστάσεων από τη ζωή του Προδρόμου, της Παναγίας, μαρτύρια αγίων, η Ρίζα του Ιεσσαί και άλλα. Πάνω από την κύρια, δυτική είσοδο εικονίστηκε ο δεύτερος κτήτορας και ηγούμενος της μονής Παύλος, σε προσκύνηση μπροστά στην Παναγία, ενώ πάνω από την είσοδο μεταξύ νάρθηκα και εξωνάρθηκα εικονίστηκαν οι ψυχές των δικαίων σαν σπαργανωμένα βρέφη στο χέρι του Θεού.
Η εξαιρετική ποιότητα των τοιχογραφιών και των ψηφιδωτών των Αγίων Αποστόλων κατατάσσουν το μνημείο ανάμεσα στα σημαντικότερα έργα της εποχής των Παλαιολόγων, σε στενή σχέση με τη Μονή της Χώρας στην Κωνσταντινούπολη.
Μετά την άλωση της Θεσσαλονίκης από τους Οθωμανούς το μοναστήρι παρέμεινε χριστιανικό έως τη δεκαετία του 1520, οπότε και μετατράπηκε από τον Kezeri Kasim Pasa σε μουσουλμανικό τέμενος, το Cezeri Kasim ή Soyuk Su Camii (τζαμί του κρύου νερού) που αποτέλεσε το κέντρο της ομώνυμης μουσουλμανικής συνοικίας.
Ο ναός συγκαταλέγεται στον κατάλογο μνημείων παγκόσμιας κληρονομιάς της UNESCO (Paleochristian and Byzantine Monuments of Thessalonika). Στερεωτικές εργασίες πραγματοποιήθηκαν στο μνημείο μετά τους σεισμούς του 1978.
