Στους βυζαντινούς χρόνους ανάμεσα στις πόλεις-κάστρα που ξεχώρισαν για την θέση και την ικανότητά τους είναι και η Εδεσσα "Το θεοφρούρητο κάστρο των Βοδενών". Απο τις πολλαπλές καταστροφές μόνο δύο μνημεία σώζονται απο τους βυζαντινούς χρόνους, ο ναός της Κοίμησης της Θεοτόκου (Παλαιά Μητρόπολη και ο ναός του Πέτρου και Παύλου).

Η παλαιά Μητρόπολη βρίσκεται στην συνοικία Βαρόσι, ανάμεσα στο Μητροπολιτικό Μέγαρο και το Παρθεναγωγείο. Η ανέγερσή της τοποθετείται στο δεύτερο μισό του 14ου αι, λίγο πριν την κατάληψη της Εδεσσας απο τους Τούρκους. Είναι μία περίοδος που ανθεί η παλαιολόγεια τέχνη και παρατηρείται ανέγερση μεγάλου αριθμού ναών και κτιρίων.

Το κτίσμα είναι Τρίκλιτη ξυλόστεγη βασιλική του 14ου αιώνα, αφιερωμένη στο Χριστό, Σοφία και Λόγο του Θεού. Ο βόρειος και ο νότιος τοίχος της εκκλησίας είναι επισκευασμένος στα μέσα του 17ου αιώνα, ενώ ο μεταγενέστερος νάρθηκας είναι κτίσμα της δεκαετίας του 1920. Τοιχογραφίες διατηρούνται στο ιερό βήμα, στις επιφάνειες επάνω από τις κιονοστοιχίες, στα εσωρράχια των τόξων και τους πεσσούς. Οι παλαιότερες τοιχογραφίες χρονολογούνται γύρω στα 1380. Αξιόλογο είναι το ξυλόγλυπτο τέμπλο του ναού, των μέσων του 18ου αιώνα, με εικόνες του ζωγράφου Αποστόλη Λογγιανού Βοδενιότη (1761).

Την δεκαετία του 1970 έγιναν εκτεταμένες αναστηλωτικές εργασίες, κατά τις οποίες απομακρύνθηκαν από τον κυρίως ναό προσθήκες του 1920, που αλλοίωναν τη μορφή του. Στο ίδιο πνεύμα, έγιναν εργασίες και στο νάρθηκα που ολοκληρώθηκαν το 1997.

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

Αξιόλογοι θεωρούνται οι κίονες, οι οποίοι προέρχονται απο παλαιότερο ναό. Ειδικά ο ανατολικός κίονας έχει ιδιαίτερο ενδιαφέρον ενώ παρουσιάζει πολλές ομοιότητες με αντίστοιχο της Ραβέννας. Επίσης αξιόλογα θεωρούνται τέμπλο και ο επισκοπικός θρόνος (18ος αι). Σημαντικές ακόμα είναι οι τοιχογραφίες οι οποίες παρουσιάζονται σε δύο στρώματα  με τις παλαιότερες να χρονολογούνται τον 14ο αι ενώ οι νεώτερες τον 17ο αι. Τέλος σώζεται κτητορική επιγραφή ανάμεσα στις τοιχογραφίες του 14ου αι με τα ίχνη (Η ΣΟ)ΦΙΑ ΤΟΥ Θ(ΕΟ)Υ που επαληθεύουν την παράδοση και επιβεβαιώνουν τα ιστορικά στοιχεία για αφιέρωμα του ναού στην Σοφία του Θεού.