Κτίστηκε πάνω σε ρωμαϊκό κτίσμα στα τέλη 5ου - αρχές 6ου αιώνα ως καθολικό της μονής Λατόμου. Το 1430 με την άλωση της Θεσσαλονίκης μετατράπηκε σε τζαμί, ενώ το ψηφιδωτό είχε καλυφθεί με ασβεστοκονίαμα. Το 1921 αποδόθηκε στη χριστιανική λατρεία και τότε ανακαλύφθηκε το ψηφιδωτό. Το μνημείο σήμερα λειτουργεί ως ναός.

Αρχικά τετράγωνο κτίσμα με κόγχη στα ανατολικά και είσοδο στα δυτικά. Μικρά τετράγωνα διαμερίσματα στις τέσσερις γωνίες του κτιρίου έδιναν στην κάτοψη του κυρίως ναού σχήμα ισοσκελούς σταυρού. Σήμερα λείπει όλο το δυτικό τμήμα του ναού και η είσοδος είναι στη νότια πλευρά. Από τη ζωγραφική του διακόσμηση σώζεται το περίφημο ψηφιδωτό της κόγχης, 5ου - 6ου αιώνα και τοιχογραφίες του 12ου αιώνα.

Στα 1929 έγιναν ανασκαφικές έρευνες στο εσωτερικό του ναού. Κατά καιρούς έγιναν διάφορες στερεωτικές και εξυγιαντικές επεμβάσεις. Το 1980 έγινε στερέωση του δυτικού τοίχου. Το 1991 ανακατασκευή - αποκατάσταση του προστώου στη νότια πλευρά.