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

Ο ναός, με βάση τον σωζόμενο τοιχογραφικό του διάκοσμο, χρονολογείται στο διάστημα μεταξύ των ετών 1375-1385 ή 1389, όμως διατηρούνται στοιχεία που μαρτυρούν ότι ήταν παλαιότερος, πιθανώς μεσοβυζαντινής περιόδου. Η αρχική του μορφή, με τις, κατά καιρούς, προσθήκες και επισκευές, ιδιαίτερα κατά την περίοδο της Τουρκοκρατίας, αλλοιώθηκε σε μεγάλο βαθμό, καθώς, μέχρι και τη δεκαετία του 1970, ο ναός έδινε την εντύπωση σπιτιού ή αποθήκης.

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

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