Весть о чуде быстро разнеслась по Херсонесу, его владениям и прибрежным районам. Огромное количество людей стало обращаться к Богу. Инкерман из места ссылки и заключения превратился в купель Святого Крещения. За время ссылки святого Климента было основано 75 храмов[14]. Языческие капища[15] разорялись, идолы уничтожались.
Успехи святого Климента в проповедании слова Божия дошли до императора Траяна. Язычник Траян направил своего приближенного Авфидана (по другим данным – Аверидиана) с указанием отвратить народ от христианства, мучая и убивая христиан, что тот и начал делать по прибытию в Тавриду. Но увидев, что пытки, мучения и смерть не только не устрашают, а напротив возбуждают желание умереть за Христа, Авфидан решил «заняться» святым Климентом и стал его запугивать, что если тот не откажется от своих действий, то будет подвергнут пыткам и казни.
Однако, увидев твердость святого в своей вере, Авфидан решил убить Климента. А для того, чтобы христиане не могли почитать место убиения своего епископа, приказал вывезти святого Климента на лодке в море и, привязав на шею якорь, утопить на виду всех жителей Херсонеса. Произошло это, согласно «Церковной истории» Евсевия Памфила, в третий год царствования Траяна, т. е. в 101 году.
Через некоторое время, верные ученики святого Климента Корнилий и Фив, собрав всю братию, сказали: «Помолимся все, чтобы Господь открыл нам тело мученика». Когда народ молился, то море отошло от берега на три поприща (около 4 км) и люди, подобно как израильтяне через «Чермное море[16]» прошли и нашли мраморную пещеру, наподобие церкви (люди назвали ее Ангельской церковью).
Там, в каменной раке лежало тело мученика и рядом с ним якорь, который был привязан к его шее при утоплении. Ученики хотели забрать тело мученика, но им явился святой Климент, который сказал: «Каждый год, в дни поминовения моего, будет так же отступать море на 7 дней, давая путь посуху приходящим во славу имени Господа».
Это подвигло все окрестные народы к вере в Бога. Обращающиеся в молитвах к святому Клименту больные выздоравливали, слепые прозревали, глухие начинали слышать. Согласно преданию, в один из дней памяти святого, когда море отступило и люди пошли на поклонение, один мальчик не вернулся на берег. Родители и все люди считали, что мальчик погиб. Но когда через год море снова открыло Ангельскую церковь, то все увидели мальчика живым и невредимым. Мальчик рассказал о том, что спас его и заботился о нем все время пребывания там седой старец, по описанию очень похожий на святого Климента.