Η εκκλησία των Αγίων Αποστόλων αποτελεί μνημείο παγκόσμιας πολιτιστικής κληρονομιάς της ΟΥΝΕΣΚΟ από το 1988. Εντάχθηκε στη λίστα μαζί με άλλα Παλαιοχριστιανικά και βυζαντινά μνημεία της Θεσσαλονίκης.

Ο ναός κτίστηκε στις αρχές του 14ου αιώνα μ.Χ (μεταξύ 1312 και 1315).Είναι πεντάτρουλλος σταυροειδής εγγεγραμμένος ναός.

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

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

Η επωνυμία του ναού, «Άγιοι Απόστολοι», είναι γνωστή από το 19ο αιώνα και οφείλεται στη λαϊκή δοξασία περί κάλυψης του ναού με δώδεκα θόλους, που συμβολίζουν τους δώδεκα αποστόλους.

Μετά την Απελευθέρωση της Θεσσαλονίκης από τον Ελληνικό Στρατό το 1912 αποκαλύφτηκαν οι τοιχογραφίες από το 1926 και εξής και καθαρίσθηκαν εξ’ ολοκλήρου τα ψηφιδωτά του ναού .