Η μονή δεν είναι γνωστό πότε ιδρύθηκε. Ο Βασιλείος Ψιλάκης ανέφερε ότι στη μονή συγκεντρώθηκαν επαναστάτες το 1272 για να τελέσουν δέηση πριν το οροπέδιο Λασιθίου να γίνει ορμητήριο για την επανάσταση. Ο Νίκος Ψιλάκης αναφέρει ότι αυτή η πληροφορία υπονοεί ότι η μονή υπήρχε από τη δεύτερη βυζαντινή περίοδο. Το παλιό αγιοθύριδο της μονής έχει τη χρονολογία 1241. Οι Ενετοί όμως, στα πλαίσια κατάπνιξης των επαναστάσεων, απαγόρευσαν την πρόσβαση στο οροπέδιο από το 1293 μέχρι το 1543, με αυστηρές ποινές για τους παραβάτες, ακόμη και θάνατο.[3]
Με την εκ νέου εγκατάσταση πληθυσμού τον 16ο αιώνα, στο οροπέδιο έφτασαν οι μοναχές Παλαντία και Θεοκλήτη, από την Πελοπόννησο. Η μοναχή Παλαντία, από τη μονή Παναγίας του Σπηλαίου, ίδρυσε τη μονή Κρουσταλλένιας, ενώ η μοναχή Θεοκλήτη ίδρυσε τη μονή Αγίας Πελαγίας, από την οποία πλέον σώζεται μόνο ο ναός. Μετά την κατάκτηση της Κρήτης από τους Οθωμανούς, στη μονή εγκαταστάθηκαν άντρες μοναχοί.[3] Κατά τη διάρκεια των Οθωμανικών χρόνων η μονή έγινε τόπος συνάντησης των καπετάνιων της περιοχής. Επίσης ήταν τόπος φιλοξενίας ξένων, όπως του περιηγητή Siber το 1817.[4]
Κατά τη διάρκεια της επανάστασης του 1821, η μονή λεηλατήθηκε και πυρπολήθηκε από τα τουρκοαιγυπτιακά στρατεύματα τον Ιανουάριο του 1823. Το 1834 ο A. Frabreguettes επισκέπτηκε τη μονή, η οποία σημειώνει, ακόμη δεν είχε αποκατασταθεί. Κατά τη διάρκεια της επανάστασης του 1866, η μονή ήταν έδρα της Επαναστατικής Επιτροπής των Ανατολικών επαρχιών και διέθετε αποθήκες πυρομαχικών.[4] Έτσι κατά την Μάχη του Λασιθίου (20-30 Μαΐου 1867) η μονή καταστράφηκε ξανά από τις Οθωμανικές δυνάμεις. Μετά την επανάσταση τα περισσότερα κτίρια της μονής κτίστηκαν από την αρχή.[5]
Στη μονή λειτουργούσε σχολείο από τα μέσα του 19ού αιώνα μέχρι το 1926.[4]
