Η ιστορία της Μονής αρχίζει από τα μέσα του 9^_ου αιώνα, τότε που για πρώτη φορά κτίσθηκε, από ζηλωτές Μοναχούς, στη θέση «Μένιες» του Ακρωτηρίου αυτού προς τιμή του Αγίου Γεωργίου στον ίδιο τόπο, που υπήρχε το Ιερό της θεάς Δικτύνης - Βρυτομάρτιδος Αρτέμιδος. Οι συχνές και βάρβαρες επιδρομές των πειρατών σ' εκείνη την περιοχή, και φυσικά εναντίον της Μονής, ανάγκασαν τους Μοναχούς και ασκητές να ζητήσουν ασφαλέστερο τόπο μοναχικής ζωής. Έτσι ήλθαν νοτιότερα και σχεδόν στη «ρίζα» του Ακρωτηρίου κατά το 13ο αιώνα και έκτισαν το μικρό Μοναστήρι, που σήμερα είναι το Κοιμητήριο της Μονής.

Δεν έχουμε γραπτές μαρτυρίες για το ξεκίνημα του ιερού προσκυνήματος της Χρυσοσκαλίτισσας. Η παράδοση αναφέρει ότι η ιερότητα του χώρου αρχίζει με την παρουσία (εύρεση) της εικόνας της Κοίμησης της Θεοτόκου σε κόγχη του βράχου. Η εικόνα αυτή κρύφτηκε εδώ πιθανότατα την εποχή της εικονομαχίας 726-842 μ.Χ. Λέγεται μάλιστα ότι βρέθηκε από ένα γεωργό που έβλεπε σαν όραμα φλόγα καντηλιού τα βράδια. Πριν κτισθεί η Χρυσοσκαλίτισσα στη θέση της υπήρχε άλλος ναός στο όνομα της Κοίμησης της Θεοτόκου. Ηταν προσκολλημένος σε σπηλαιώδη βράχο. Στη σκέπη του βράχου υπήρχε και άλλος συνεχόμενος ναός της Αγίας Τριάδος.