Точное время основания монастыря сегодня не берется никто. В ученом мире существуют две версии.

Согласно первой версии, монастырь основали греческие монахи-иконопочитатели не позднее VIII века, бежавшие из Византии. Ущелье, чем-то похожее на древний Афон, напомнило им родные края, и поразило своей красотой. К тому же, здесь находился источник пресной воды. И первые монахи, поселившиеся здесь, выдолбили в скале храм и пещеры-кельи - свои новые жилища.

Сторонники второй версии относят основание Успенского монастыря к XV веку. Возможно, ранее монастырь находился в пещерах у южных ворот крепости Кырк-Ор (Чуфут-Кале). Но после захвата крепости турками в 1475 году он был перенесен на новое место. Эту версию поддерживал также известный ученый XIX века, исследователь Крыма А.Л. Бертье-Делагард, ссылаясь на древние рукописи, которые не дошли до наших дней.

Относительно основания монастыря, существует также три предания.

Согласно первому на месте монастыря пастухом была найдена икона Богородицы, которая при перенесении на новое место каждый раз возвращалась на скалы, где была обретена. Люди поняли, что здесь необходимо устроить храм и, поскольку обретение состоялось 15 августа в праздник Успения Богородицы, назвали его Успенским.

Второе предание говорит о том, что на жителей округи нападал злой змий. Однажды, после усердных молитв Богородице, на одной из скал люди заметили горящую свечу. Прорубив к ней ступени, жители нашли икону Богородицы и лежащего перед ней мёртвого змия.

Третье предание гласит, что икона Богородицы, обнаруженная на скалах ущелья, перенесена туда из византийского монастыря близ Трапезунда.

Древний пещерный храм и сам монастырь получили название Успенского в честь великого события - Успения Пресвятой Богородицы.