Ο ναός της Παναγίας Γοργοεπηκόου —γνωστός στους Θεσσαλονικείς ως Παναγούδα— ανεγέρθηκε το 1818 στον τύπο της μεταβυζαντινής ξυλόστεγης βασιλικής με γυναικωνίτη. Στην ημιυπαίθρια εξωτερική στοά στη δυτική όψη του ναού έχουν χρησιμοποιηθεί πρωτοβυζαντινά και βυζαντινά αρχιτεκτονικά μέλη. O ναός κατέλαβε τη θέση παλαιότερου ομώνυμου ναού που καταστράφηκε από πυρκαγιά το 1817.
Σύμφωνα με αρχειακές πηγές της εποχής, ο μεγάλων διαστάσεων ναός, αφιερωμένος στο Γενέσιο της Θεοτόκου, σχεδιάστηκε και ανεγέρθηκε περισσότερο διευρυμένος από ό,τι επιτρεπόταν από τις σύγχρονες διατάξεις της οθωμανικής διοίκησης και αποτελούσε το κέντρο της ευάριθμης ομώνυμης χριστιανικής συνοικίας. Από το ναό προέρχονται σημαντικά βυζαντινά κειμήλια της πόλης όπως ο χρυσοκέντητος επιτάφιος της παλαιολόγειας περιόδου που φυλάσσεται στο μουσείο Βυζαντινού Πολιτισμού, γεγονός που καθιστά πολύ πιθανή την ύπαρξη στη θέση του κάποιας βυζαντινής μονής, η οποία έχει παλαιότερα ταυτιστεί με γνωστή από βυζαντινές πηγές του 12ου έως και 14ου αι., αρχικά ανδρική και εν συνεχεία γυναικεία, μονή με την επωνυμία «Βασιλικόν».
