Ο ναός της Παναγίας βρίσκεται μέσα στον οικισμό της Πατσού. Η ευρύτερη περιοχή έχει έντονο αρχαιολογικό ενδιαφέρον, καθώς στο φαράγγι της Πατσού υπάρχει ιερό που στα ιστορικά χρόνια ήταν αφιερωμένο στον Κραναίο Ερμή, ενώ η λατρευτική χρήση του μαρτυρείται από πολύ νωρίτερα, ήδη από το τέλος της εποχής του Χαλκού (περίπου 1200 π.Χ.), σε πιθανή σύνδεση με γονιμική θεότητα.

Ο ναός είναι αφιερωμένος στη Γέννηση της Παναγίας. Η παλαιότερη βιβλιογραφία τον είχε κατατάξει στους μεσοβυζαντινούς (11ος -12ος), με εκτεταμένη ανακατασκευή στον 14ο αιώνα. Όπως προέκυψε από τις εργασίες αποκατάστασης του μνημείου κατά τα έτη 2012-2014, η αρχική και κύρια κατασκευαστική φάση του ναού χρονολογείται στο πρώτο τέταρτο του 14ου αιώνα, με πολλές μικρές ή μεγαλύτερες μετατροπές κατά τους επόμενους αιώνες, οι οποίες ωστόσο δεν άλλαξαν την αρχιτεκτονική δομή του ναού.

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

Ο τοιχογραφικός διάκοσμος του ναού χρονολογείται στο πρώτο μισό του 14ου αιώνα και αποτελεί έργο ενός πολύ ικανού συνεργείου, που συνδέεται με τις σύγχρονες τάσεις της παλαιολόγειας τέχνης. Μεγάλο μέρος του αποτοιχίσθηκε τη δεκαετία του 1970 και μέχρι πρόσφατα εκτίθεντο στη Συλλογή της Αγίας Αικατερίνης στο Ηράκλειο. Το 2011 οι τοιχογραφίες επέστρεψαν στο Ρέθυμνο, συντηρήθηκαν και πρόκειται να εκτεθούν στο Νέο Αρχαιολογικό Μουσείο της Πόλης. Το εικονογραφικό πρόγραμμα περιλάμβανε σκηνές από το Χριστολογικό και θεομητορικό κύκλο, με την Παναγία Βρεφοκρατούσα στην αψίδα και πιθανόν το Χριστό, στο χαμένο σήμερα τρούλο. Ο βίος του Αγίου Νικολάου ιστορούνταν σε περίπου δέκα σκηνές, ενώ στα χαμηλά τμήματα των τοίχων υπήρχαν μεμονωμένες μορφές όρθιων μετωπικών αγίων. Από τις παραστάσεις ξεχωρίζει η σκηνή της Απογραφής του Κυρηνίου, η οποία μέχρι σήμερα έχει εντοπιστεί σε τέσσερις μόνο παραστάσεις, των οποίων η ζωγραφική συνδέεται με την τέχνη της Πρωτεύουσας.

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

Στο ναό της Παναγίας, κατά τα έτη 2012-2014 έγιναν εκτεταμένες εργασίες στερέωσης των τοιχοποιιών, αποκατάστασης και διαμόρφωσης του περιβάλλοντα χώρου καθώς και συντήρησης του τοιχογραφικού διακόσμου, στο πλαίσιο του Προγράμματος Διασυνοριακής Συνεργασίας Ελλάδα Κύπρος 2007-2013.