Возрождение Кизилташской обители началось через 51 год после присоединения Крыма к России. В 1825 году в водах кизилташского пещерного источника пастух-татарин обнаружил плавающую деревянную икону Божьей Матери. Впоследствии он отдал ее греку-купцу Пластару, а тот, в свою очередь, прибыв в Феодосию, передал икону протоиерею Иосифу. Молва о чуде обретения иконы моментально распространилась по всему Восточному Крыму. В грот урочища Кизилташ нескончаемым потоком стали стекаться паломники. Вода и грязь источника были признаны целебными. В 1837 в гроте уже была часовня, где, как сообщает академик П.Кеппен, на столе, заменяющем алтарь, при иконе лежал обломок мраморной плиты с изображением лика какого-то святого.
Позже у пещерной часовни семь лет (примерно с 1844 по 1851 гг.) провела в молитве и одиночестве девушка болгарка Константина из с. Кишлав (Курское). Когда в Кизилташе остановились два странствующих богомольца, она перешла в урочище Топлы, где позже был основан Троице-Параскевиевский женский монастырь (1864 г.). Там Константина приняла постриг и была наречена Параскевой (умерла в 1874 г.). Два упомянутых выше странствующих богомольца — бывший крепостной крестьянин Калужской губернии Андроник и отставной вахмистр Пантелеймон в 1851 году построили вблизи грота с целебным источником монашеский скит, представлявший собой временное жилище, и крошечную часовню из плетня и глины. В 1853 году несколько дней в урочище Кизилташ провел архиепископ Херсонский и Таврический Иннокентий. Он освятил эту небольшую часовню как будущий храм во имя Свт. Стефана Сурожского и дал благословение на строительство здесь монастыря.
