Δεν έχουμε γραπτές μαρτυρίες για το ξεκίνημα του ιερού προσκυνήματος της Χρυσοσκαλίτισσας. Η παράδοση αναφέρει ότι η ιερότητα του χώρου αρχίζει με την παρουσία (εύρεση) της εικόνας της Κοίμησης της Θεοτόκου σε κόγχη του βράχου.
Η εικόνα αυτή κρύφτηκε εδώ πιθανότατα την εποχή της εικονομαχίας 726-842 μ.Χ. Λέγεται μάλιστα ότι βρέθηκε από ένα γεωργό που έβλεπε σαν όραμα φλόγα καντηλιού τα βράδια. Πριν κτισθεί η Χρυσοσκαλίτισσα στη θέση της υπήρχε άλλος ναός στο όνομα της Κοίμησης της Θεοτόκου. Ηταν προσκολλημένος σε σπηλαιώδη βράχο. Στη σκέπη του βράχου υπήρχε και άλλος συνεχόμενος ναός της Αγίας Τριάδος.
Κάποτε αποφάσισαν να κτίσουν μεγαλύτερη την εκκλησία και σκέφτηκαν η ανέγερση να γίνει στους πρόποδες του βράχου, γιατί, έτσι θα απέφευγαν τις δυσκολίες και τον κόπο του ανεβάσματος των υλικών. Λέγεται ότι ενώ η εικόνα είχε μεταφερθεί αλλού, μυστηριακά γυρνούσε στη θέση που είχε πρωτοβρεθει. Όλοι θεώρησαν το γεγονός θέληση της Παναγίας να κτισθεί ο ναός πάνω στο βράχο, πράγμα που έγινε.
Το όνομα το πήρε, (κατά την παράδοση πάντα), από ένα χρυσό σκαλοπάτι, το τελευταίο από τα ενενήντα οκτώ που είχε τότε. Τα πρώτα χρόνια της Τουρκοκρατίας, ο Πατριάρχης αναγκάστηκε να πουλήσει τα κτήματα της Μονής καθώς και το χρυσό σκαλοπάτι, για να πληρώσει τους βαρύτατους φόρους που είχε επιβάλει ο σουλτάνος, με συνέπεια την ερήμωση του Μοναστηριού. Την ημέρα του Πάσχα του έτους 1824 έγινε η μεγάλη σφαγή στο Λαφονήσι από τους Τουρκοαιγύπτιους. Στο πέρασμά τους χάλασαν δέκα εκκλησίες της περιοχής. Πέρασαν και από τη Χρυσοσκαλίτισσα που ήταν έρημη. Ήθελαν να την ισοπεδώσουν, αλλά τους εμπόδισε ένα σμήνος μελισσών, που είχε για κυψέλη την κόγχη που βρίσκεται το εικονοστάσι το οποίο συναντούμε, όταν ανεβαίνουμε στη Μονή.
Πρώτος, που κατοίκησε μετά την ερήμωση, ήταν ένας μοναχός Ιωαννίκιος από τα Κύθηρα. Μετά το θάνατό του ακολούθησε νέα ερήμωση. Το 1855 άρχισε η αναβίωση της Μονής με την εγκατάσταση του μοναχού Μανασσή Καραγιαννάκη. Καταγόταν από την οικογένεια των Γλυνιάδων του χωριού Ασκύφου Σφακίων. Από συνδρομές, άρχισε την ανακαίνιση της ερειπωμένης Μονής και από τα ερείπια έκτιζε νέα κτίρια. Μετά από μερικά χρόνια ήλθε στη Μονή ο Εμμανουήλ Καλιτσουνάκης καταγόμενος από το χωριό Τζιτζιφιά. Χειροτονήθηκε ιερομόναχος και πήρε το όνομα Μελέτιος. Ο Μανασσής έφερε την αργυρή εικόνα της Παναγίας από τη Σμύρνη. Το 1866 πέθανε ο Μανασσής αφήνοντας, μια μικρή περιουσία που είχε αγοράσει από συνδρομές και χρήματα. Ο Μελέτιος συνέχισε επάξια το έργο του προϊσταμένου του Μανασσή και επί των ημερών του το μοναστήρι ήταν ιδιόρρυθμο. Τον Μελέτιο διαδέχθηκε ο Μανασσής κατά κόσμον Μιχαήλ Κατερινάκης από το Αμυγδαλοκεφάλι. Επί Μανασσή χάλασαν την παλιά εκκλησία και έκοψαν το βράχο για τη δημιουργία χώρου για το χτίσιμο της εκκλησίας που βλέπουμε σήμερα. Το κτίριο άρχισε με προθυμία και ζήλο την 9η Μαίου 1894 και περατώθηκε την 10η Αυγούστου του ίδιου έτους. Τα εγκαίνια έγιναν την ημέρα της εορτής της Κοίμησης της Θεοτόκου (15 Αυγούστου). Το 1897 ο Μανασσής έφυγε στο εξωτερικό και τον διαδέχθηκε ο Γρηγόριος Πλοκαμάκης (από Πλοκαμιανά) που υπηρέτησε τη Μονή περισσότερο από μισό αιώνα. Αυτόν αναφέρει ο Καζαντζάκης στο έργο του «Αναφορά στον Γκρέκο».
Το 1900 η Μονή διαλύθηκε μαζί με άλλες μονές της Κρήτης. Επανιδρύεται σαν γυναικεία το 1940. Μετά την κατάληψη της Κρήτης από τους Γερμανούς, φιλοξενήθηκαν στη Μονή αρκετοί στρατιώτες, αγωνιστές και άλλοι που ανήκαν στην αγγλική κατασκοπεία. Το 1943 εγκαταστάθηκαν οι Γερμανοί κατακτητές στη Μονή (αφού έδιωξαν τους μοναχούς). Τότε πολυβολήθηκαν από αγγλικό αεροπλάνο. Σημάδια του πολυβολισμού φαίνονται σε χαμηλή εικόνα του τέμπλου. Η ζωή ξαναγύρισε μετά την 27η Ιανουαρίου 1944, ημέρα που έφυγαν οι Γερμανοί. Αυτή η ζωή συνεχίζεται αδιάκοπα από τους φιλόξενους και δραστήριους μοναχούς που προσφέρουν τις υπηρεσίες τους και κρατούν ζωντανό το ιερό αυτό προσκύνημα.
