Cette icône avait probablement été cachée à l’époque de la querelle iconoclaste (726-842 ap. J.-C.). On raconte même qu’elle fut découverte par un cultivateur qui le soir voyait une flamme de bougie en vision. Avant la construction de Panagia Chrysoskalitissa, il existait au même endroit une autre église dédiée à la Dormition. Cette église était accolée à une cavité rocheuse. Une autre église, dédiée à la Sainte Trinité, se trouvait sur le sommet du rocher.
On décida ensuite de bâtir une église plus grande au pied du rocher afin d’éviter les difficultés et les efforts inhérents au transport des matériaux. On raconte que l’icône qui avait alors été transportée dans un autre endroit revenait mystérieusement là où elle avait été découverte. Tous considérèrent donc que la volonté de la Vierge était que l’église soit construite sur le rocher, ce qui se passa.
Toujours selon la tradition, l’église doit son nom de Chrysoskalitissa à une marche en or, la dernière des quatre-vingt-dix-huit qu’elle comptait alors. Les premières années de l’occupation ottomane, le Patriarche fut contraint de vendre les terres du monastère ainsi que la marche en or pour payer les très lourds impôts que le sultan lui réclamait. Ainsi, le monastère fut abandonné. En 1824, le jour de Pâques, les Turcs Égyptiens se livrèrent à un effroyable massacre à Elafonisi. Sur leur passage, ils détruisirent dix églises de la région. Ils passèrent également par Chrysoskalitissa qui était déserte. Ils tentèrent de la raser mais en furent empêchés par un essaim d’abeilles qui avaient pour ruche l’abside située dans l’iconostase que l’on voit en montant au monastère.
Le premier à revenir au monastère fut un moine de Cythère, Ioannikios. Après sa mort, le monastère fut à nouveau déserté. En 1855, il retrouva une certaine activité lorsque s’y installa le moine Manassis Karagiannakis, originaire de la famille des Glyniades du village Askyfou de Sfakia. Grâce à des dons, il commença de restaurer le monastère en ruine puis construisit de nouveaux bâtiments. Quelques années plus tard, Emmanouil Kalitsounakis, originaire du village de Tzitzifia, rejoignit le monastère. Il fut ordonné prêtre et prit le nom de Meletios. Manassis rapporta de Smyrne l’icône en argent de la Vierge. À sa mort en 1866, Manassis laissa un petit patrimoine qu’il avait acquis grâce à des dons.
Meletios poursuivit dignement l’œuvre de son supérieur Manassis, tandis que chaque moine pouvait vivre dans le monastère à sa manière. Michail Katerinakis, originaire d’Amigdalokefali, lui succéda et reprit le nom de Manassis. À l’époque de Manassis, l’ancienne église fut démolie et le rocher fut cassé pour dégager l’espace où se trouve l’église que l’on voit aujourd’hui. La construction commença dans l’allégresse le 9 mai 1894 et s’acheva le 10 août de la même année. L’inauguration eut lieu le jour de la fête de la Dormition de la Vierge (15 août). En 1897, Manassis partit à l’étranger. Grigorios Plokamakis (de Plokamiana) lui succéda et resta à la tête du monastère pendant plus d’un demi-siècle. C’est ce qu’indique Kazantzakis dans sa Lettre au Greco.
En 1900, le monastère fut dissout, comme d’autres monastères en Crète. Il ouvrit à nouveau ses portes comme couvent de religieuses en 1940. Sous l’occupation allemande, le monastère accueillit plusieurs militaires, combattants et autres membres de l’espionnage anglais. En 1943, les Allemands s’installèrent dans le monastère (après en avoir chassé les moines). Ils furent alors mitraillés par l’aviation anglaise. Des traces de tirs sont encore visibles sur une icône en bas de l’iconostase. La vie reprit son cours le 27 janviers 1944, lorsque les Allemands partirent. Elle se poursuit désormais normalement grâce aux moines hospitaliers et actifs qui offrent leurs services et maintiennent en vie ce lieu sacré de pèlerinage.
