В одной из долин, расположившейся у скального хребта Кизил-Таш (по-татарски «красный камень»), неподалеку от села Краснокаменка, и был основан в 1850-х годах мужской монастырь в честь святителя Стефана Сурожского.
Христианская же история этого места началась еще за тысячу сто лет до этого события — в VIII веке от Рождества Христова. И самым тесным образом она связана с именем святого угодника Божия — святителя Стефана Сурожского.
Внизу у моря в живописной бухте в те времена шумел торговой жизнью богатый и красивый город и порт Сурож (ныне Судак), в котором уже тогда действовали христианские храмы. Была здесь и епископская кафедра. В 724 году правящий сурожский епископ преставился ко Господу. Тогда жители города пришли в Царьград к Патриарху Герману с просьбой поставить им епископа. Во время выбора кандидатов среди просителей возникли несогласия: одни хотели одного, другие — другого. Но все сходились в том, что нужен был епископ, могущий искусно управлять Церковью, поскольку в их городе возникли и умножаются всевозможные ереси.
Пока Патриарх Герман размышлял, кого бы назначить на сурожскую кафедру, ему явился ангел Господень и повелел для этой цели найти благочестивого монаха Стефана — добронравного, смиренного, а также очень грамотного и мудрого человека. Следует также сказать, что Стефан, желая безмолвной жизни, задолго до этих событий оставил монастырь, в котором принял иноческий постриг, и, найдя никому не известное уединенное место, прожил там довольно много времени в посте и молитве.
Ангел также явился и Стефану. Как говорится в Житии святого, он сказал отшельнику: «Я ангел Господень и послан от Христа Спасителя возвестить тебе радость и повелеть идти в город Сурож, чтобы ты научил людей Христовой вере. Завтра Патриарх призовет тебя и, посвятив, пошлет туда архиепископом, ты же не ослушайся его, да не прогневаешь Бога».
На то время в Византии набрала силу иконоборческая ересь во главе с императором Львом Исавром. Многих из тех, кто почитал иконы, ссылали или даже убивали. Святой патриарх Герман пытался увещевать Льва Исавра, но усилия его были напрасны: вскоре и он по указу императора оказался в заточении.
В Сурож также было отправлено строжайшее императорское повеление не поклоняться иконам и кресту. На что Стефан Сурожский твердо ответил, что он не позволит своему народу отступить от закона Христова. Стефана схватили, его предали мучениям, а затем бросили в тюрьму. Только через несколько лет сын умершего Льва Константин Копроним освободил Стефана из заточения. Он не только освободил и наградил его за все, что ему пришлось претерпеть, но снова назначил его архиепископом в Сурож, где затем тот управлял делами верующих уже до самой своей кончины в 750 году.
Святителя Стефана Сурожского погребли в Софийском соборе города Сурожа. Возле его святых мощей Господь творил чудеса: многие люди исцелялись от своих душевных и телесных недугов.