Η Μονή της Παναγίας της Αντιφωνήτριας, σύμφωνα με την παράδοση, χτίστηκε κατά τη δεύτερη δεκαετία του 11ου αιώνα από τον όσιο Ιωάννη τον Ξένο και Ερημίτη. Πρόκειται για ένα λόγιο μοναχό, που έδρασε στην περιοχή της δυτικής Κρήτης κατά τα τέλη του 10ου και το πρώτο μισό του 11ου αιώνα. Ίδρυσε εννέα μονές στην περιοχή των σημερινών νομών Ρεθύμνου και Χανίων, όπως πληροφορούμαστε από τη χειρόγραφη παράδοση του βίου και της διαθήκης του. Το σπουδαιότερο από τα ιδρύματα του Ξένου, που αποτελεί μέχρι σήμερα ένα από τα μεγαλύτερα θρησκευτικά προσκυνήματα της Κρήτης, είναι η Μονή της Παναγίας της Αντιφωνήτριας, στην οποία μετά το θάνατό του αφιέρωσε όλα τα άλλα ιδρύματά του. Σε επίσκεψή του στην Κωνσταντινούπολη, γύρω στα 1030 φρόντισε για την εξασφάλιση αυτοκρατορικών και πατριαρχικών προνομίων και έφερε κατά την επιστροφή του στην Κρήτη εικόνες χειρόγραφα και άλλα πολυτελή κειμήλια.

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

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

Το δεύτερο στρώμα τοιχογράφησης του καθολικού εντοπίζεται στον κύλινδρο της κόγχης με τους συλλειτουργούντες ιεράρχες και στη δυτική κεραία του σταυρού με τη Βαϊοφόρο, την Εις Άδου Κάθοδο, την Προδοσία και τον Ενταφιασμό. Χρονολογείται στις αρχές του 13ου αιώνα και παρά τα κάποια στοιχεία λαϊκότητας, που εντοπίζονται επιβεβαιώνει τον οικουμενικό χαρακτήρα της κομνήνειας τέχνης, που είχε επικρατήσει και στην Κρήτη κατά το 12ο αιώνα.

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

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