Ученые точно не могут сказать, когда был возведен монастырь. Но приблизительная дата его основания – 8-9 века, когда массово переселялись христиане, которые поклонялись иконам. Их преследовали византийские иконоборцы. При этом другие исследователи и археологи считают, что Пещерный монастырь был возведен намного позже, а именно в 14-15 веках.
После многочисленных раскопок стало известно, что пещеры и старинные кельи в скале были высечены людьми в совершенно разное время. Есть поверье, что самая давняя пещера высечена легендарным Святым Климентом. А император того времени Траян в 98 году сослал этого Римского Папу в каменоломни Херсонеса за то, что тот проповедовал христианство. Но и здесь Климент продолжил проповедовать, после чего в 101 году его утопили в море.
После этого пещеры в скалах стали появляться снова и снова. Здешние жители жили здесь, использовали пещеры, как подсобные помещения. А в Загайтанской скале такие уникальные пещеры располагались в несколько ярусов, поэтому ученые предполагают, что в данном месте было целое поселение.
В Средние века весь район считался центром монашеской жизни. Около 30 храмов и 9 пещерных комплексов здесь были обнаружены в разные времена. Один из таких храмов располагается с левой стороны от тоннеля в Инкерманский монастырь. Он действовал вплоть до прихода советской власти. Но даже после развала Союза он не возобновил свою деятельность, и до сих пор закрыт для посещений и паломничества.
Кроме того, на территории пещерного монастыря располагался святой источник, который был обнаружен самим Климентом. Но в последние годы 20 века в карьере по добыче известняка его нарушили, из-за чего образовалось озеро.