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

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

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

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

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

Ο μεσοβυζαντινός ναός της Παναγίας στην Κυριάννα με τις διαδοχικές επεμβάσεις των χρόνων της βενετοκρατίας, που αλλοίωσαν όχι μόνο τον αρχικό αρχιτεκτονικό τύπο, αλλά και τα επιμέρους διακοσμητικά στοιχεία, αποτελεί ένα ιδιαιτέρως ενδιαφέρον παράδειγμα των διεργασιών, που πραγματοποιήθηκαν στο χώρο της εκκλησιαστικής αρχιτεκτονικής στην Κρήτη ως επίδραση της επαφής με τη Δύση τόσο όσον αφορά στα πρωιμότερα υστερογοτθικά στοιχεία, όσο και στις μεταγενέστερες επιδράσεις του Μανιερισμού. Η διαχρονική σημασία του μνημείου είναι αναγνώσιμη σήμερα με την ανάδειξη των διάφορων οικοδομικών φάσεων κατά τις πρόσφατες αναστηλωτικές εργασίες, που πραγματοποιήθηκαν από την 28η ΕΒΑ στα πλαίσια του Περιφερειακού Επιχειρησιακού Προγράμματος Κρήτης του Γ΄ Κοινοτικού Πλαισίου Στήριξης.