Στην αρχή της οδού Ολύμπου, κοντά στα δυτικά τείχη της Θεσσαλονίκης και νότια της Ληταίας Πύλης, βρίσκεται ο ναός των Αγίων Αποστόλων. Ο πυλώνας νότια του ναού και η κινστέρνα στα βορειοδυτικά μαρτυρούν ότι αποτελούσε καθολικό μοναστηριού.

Η επιγραφή ''Πατριάρχης και κτήτωρ'' στο υπέρθυρο της εισόδου, τα μονογράμματα (συμπιλήματα) στα κιονόκρανα της δυτικής όψης και οι κεραμοπλαστικές επιγραφές στη δυτική και νότια όψη αναφέρουν τον Πατριάρχη Νίφωνα Α' (1310-1314) ως ιδρυτή. Γραπτή επιγραφή στον ανατολικό τοίχο του νάρθηκα μνημονεύει τον ίδιο Πατριάρχη και το μαθητή του ηγούμενο Παύλο ως πρώτο και δεύτερο κτήτορα, αντίστοιχα, ''της σεβασμίας Μονής ταύτης''. Η απεικόνιση του Παύλου δεομένου μπροστά στην ένθρονη Θεοτόκο, στο υπέρθυρο της εισόδου προς τον κυρίως ναό, και οι θεομητορικές σκηνές που κοσμούν τη στοά ενισχύουν την υπόθεση ότι πρόκειται για βυζαντινή μονή αφιερωμένη στην Παναγία, ίσως τη Μονή της Θεοτόκου Γοργοεπηκόου.

Το μνημείο ανήκει στον τύπο των σύνθετων πεντάτρουλλων τετρακιόνιων σταυροειδών εγγεγραμμένων ναών με νάρθηκα και περίστωο με δύο παρεκκλήσια ανατολικά. Τα πολλαπλά επίπεδα όπου αποτυπώνεται έντονα το σημείο του σταυρού, η πλινθόκτιστη ανωδομή, οι ραδινοί τρούλοι, οι πολύπλευρες κόγχες του ιερού βήματος, τα αψιδώματα, τα βαθμιδωτά τόξα, οι ημικιονίσκοι, τα δίλοβα παράθυρα και τα τρίβηλα ανοίγματα συντελούν στη δημιουργία ενός κομψού και ανάλαφρου συνόλου. Ο κεραμοπλαστικός διάκοσμος στην ανατολική πλευρά προσδίδει ζωγραφική όψη στο αρχιτεκτόνημα.

Αριστουργηματικά ψηφιδωτά της εποχής του Νίφωνα σώζονται αποσπασματικά στα υψηλότερα σημεία του κυρίως ναού: ο Παντοκράτορας και οι προφήτες στον τρούλο, οι Ευαγγελιστές στα σφαιρικά τρίγωνα, το Δωδεκάορτο στις καμάρες και το δυτικό τοίχο και άγιοι μάρτυρες. Πρόκειται για το τελευταίο ψηφιδωτό σύνολο της Θεσσαλονίκης και από τα τελευταία στο Βυζάντιο, προτού αρχίσει η πτωτική πορεία της αυτοκρατορίας. Εικονογραφικά συνδέεται με κωνσταντινουπολίτικα σύνολα, όπως της Μονής της Χώρας και της Μονής Παμμακαρίστου, αλλά τεχνοτροπικά ο εκφραστικός ρεαλισμός που κυριαρχεί σκιαγραφεί το καλλιτεχνικό περιβάλλον που επιχωριάζει στη Θεσσαλονίκη και επηρεάζει ολόκληρη τη Μακεδονία κατά την παλαιολόγεια ανναγένηση.

Το εικονογραφικό πρόγραμμα συμπληρώθηκε με τοιχογραφίες υψηλής καλλιτεχνικής ποιότητας, στα χαμηλότερα τμήματα του κυρίως ναού, το νάρθηκα, το περίστωο και το βόρειο παρεκκλήσι του Προδρόμου με σκηνές από την Παλαιά και Καινή Διαθήκη και με θέματα συμβολικά ή εμπνευσμένα από την υμνογραφία. Ξεχωρίζουν η Ρίζα του Ιεσσαί, δηλαδή το γενεαλογικό δένδρο της Θεοτόκου στον ανατολικό τοίχο του νότιου περιστώου, οι προεικονίσεις της Παναγίας στο βόρειο τοίχο της ίδιας στοάς, οι ψυχές των δικαίων στο χέρι του Θεού πάνω από τη δυτική είσοδο του εσωνάρθηκα, ο ύμνος των Χριστουγέννων ''τι σοι προσενέγκωμεν Χριστέ'' στη βόρεια στοά και ο βίος του Προδρόμου στο βόρειο παρεκκλήσι. Στενή σχέση με την Κωνσταντινούπολη παρουσιάζουν οι τοιχογραφίες που αποπνέουν ιδεαλισμό, ευγένεια, χάρη και ηρεμία και συνδέονται άρρηκτα με εκείνες της Μονής της Χώρας.

Η τοιχογράφηση του ναού έχει συνδεθεί με την ηγουμενία του Παύλου ''και δευτέρου κτήτορος'', μετά το 1314 ή μεταξύ των ετών 1328-1334.

Περί το 1520-1530 η μονή μετατράπηκε σε τζαμί με την επωνυμία Σοούκ Σου Τζαμί (= τζαμί του κρύου νερού). Τα ψηφιδωτά και οι τοιχογραφίες καλύφθηκαν με επίχρισμα, αφού πρώτα αφαιρέθηκαν προσεκτικά οι χρυσές ψηφίδες. Η επωνυμία Άγιοι Απόστολοι συνδέεται με τη νεώτερη παράδοση του 19ου αιώνα.

Οι αποκαλύψεις των τοιχογραφιών πραγματοποιήθηκαν σταδιακά από το 1926 και εξής. Μετά τους σεισμούς του 1978 έγιναν εργασίες στερέωσης. Το 2002 καθαρίστηκαν τα ψηφιδωτά και αναδείχθηκε ο χρωματικός πλούτος τους.