Вскоре известия об успехах миссионерской деятельности Климента в Херсонесе дошли и до Траяна. Император был вне себя. Еще бы, на краю империи, вопреки всем смертям и расправам, вопреки всем его усилиям множилась и процветала христианская община, предводительствуемая столь авторитетным пастырем, как Климент! Сам же город Херсонес на глазах превращался в настоящую христианскую цитадель, с каждым днем увеличивающую свою силу и мощь. Решение Траяна в отношении наказания упорного епископа было на этот раз предельно кратким – смерть! Не доверяя местным херсонесским трибунам, Траян посылает в город одного из своих ближайших соратников легата Анфидиона с отрядом отборнейших легионеров. Едва ступив на херсонесскую пристань в Карантинной бухте, Анфидион начинает действовать. В первую очередь легионеры хватают епископа, одновременно начинаются и массовые избиения остальных христиан. Затем Климент был под усиленной охраной посажен в лодку и вывезен в нынешнюю Казачью бухту (подальше от города). К шее первосвященника привязали тяжелый корабельный якорь. После чего Климент был сброшен в воду и утоплен. Говорят, что последними словами, которые погибающий пастырь успел выкрикнуть, были слова из «Апокалипсиса»: «Се гряду скоро и возмездие мое со мной, чтобы воздать каждому по делам его...»
Вместе с епископом было убито в то время немало других христиан. Среди них и верный последователь и ближайший соратник Климента преподобный Фив.
Существует легенда, что Бог, услышав стенания верующих, произвел в день кончины святого Климента отлив вод от берега на семь дней, и люди ходили по дну, ища тело своего пастыря, а найдя, похоронили на маленьком песчаном островке посреди бухты.
Рукописи повествуют, будто бы чудо отлива в Казачьей бухте происходило ежегодно вплоть до VI века н.э. Место гибели епископа было очень почитаемо на протяжении нескольких столетий. Откроем старинную летопись, написанную старцем Феодосием: «...Так же город Херсонес, что у моря Понта, там претерпел мучение святой Климент, гробница его в море, где было брошено его тело. Этому святому Клименту был привязан на шею якорь, и теперь в день его памяти весь народ и священники приплывают туда, море высушивает шесть миль, и на месте, где находится гробница, раскидываются шатры и сооружается алтарь, и в течение восьми дней служатся там Литургии, и Господь совершает там много чудес: там изгоняются бесы, и если кто из одержимых получит возможность прикоснуться к якорю и прикоснется, то сейчас исцеляется».
Место погребения святого Климента было местом настоящего паломничества тех, кто посещал Херсонес. Здесь были французы, ездившие в XII веке в Киев к Ярославу Мудрому, и известный средневековый путешественник монах Гийом Рубрук, немецкий путешественник XIII века Иоган Шильтебергер, и историк Дортелли д,Асколли. Все они оставили воспоминания о Климентовой могиле и о церкви на ее месте, сооруженной, по преданию, самими ангелами. Вот как выглядит воспоминание о посещении этих мест Гийомом Робруком: «Мы прибыли в область Газарию или Кассарию, которая представляет как бы треугольник, имеющий с запада город, именуемый Керсона (Херсонес.
Христианская церковь спустя некоторое время после смерти объявила Климента святым. Так Херсонес обрел своего первого мученика, мученика, почитаемого ныне во всем христианском мире.
И все же, почему Климент был именно утоплен? Ведь в «лучших традициях» римско-византийской империи были куда более популярные казни, как-то распятие или просто побитие камнями, сожжение на костре или замуровывание в стены. Зачем надо было столько шума: снаряжать галеру, идти на ней в самую отдаленную из херсонесских бухт и там топить жертву на заведомом мелководье? В конце концов, Климента можно было утопить и гораздо ближе, причем на куда более глубоком месте? Может, это была чья-то глупая прихоть или роль сыграл его величество случай? Ни в то, ни в другое я не верю! Процедура убийства, на мой взгляд, наоборот, была продуманна и обоснованна до самых мельчайших деталей!
Целью организованного действа было не только и не столько физическое уничтожение изможденного старика, сколько проведение представления, которое наглядно бы продемонстрировало всем торжество незыблемых догм старой веры над новой. Именно для этого и было выбрано утопление. Состояться оно должно было именно на мелководье Казачьей бухты. Но почему все же именно оно?