Η Παλαιά Μητρόπολη είναι ένας από τους δύο βυζαντινούς ναούς που σώζονται στην Έδεσσα. Η ανέγερσή της τοποθετείται στο δεύτερο μισό του 14ου αιώνα, δηλαδή λίγο πριν από την κατάληψη της Έδεσσας από τους Τούρκους. Αρχικά ο ναός ήταν αφιερωμένος στον Ιησού Χριστό με το όνομα Αγ. Σοφία. Αργότερα, στο 17ο αιώνα, μετονομάσθηκε σε εκκλησία της Υπεραγίας Θεοτόκου (Κοίμηση της Θεοτόκου) για να αποτραπεί η μετατροπή της σε τζαμί. Ως Μητροπολιτικός ναός (Μητρόπολη) αποκαλείται στους νεότερους χρόνους.

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

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

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

Ζητούμενο του έργου ήταν η καθαίρεση του νεωτερικού νάρθηκα και η αποκατάσταση του παλαιού, σύμφωνα με λεπτομερή τεκμηρίωση που αφορούσε σε αρχαιολογική έρευνα και συγκριτική μελέτη μνημείων της ίδιας περιόδου στο χώρο της Μακεδονίας.

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