Для крымских католиков и православных особое значение имеют двое святых — это мученики св.Клемент (+ 97) и св.Мартин (+ 656).
Римская Церковь присутствовала на этой земле с самых ранних веков христианской эры. Гонения, чинимые императорами, забросили сюда Папу Римского Климента I, бывшего четвертым по преемству Епископом Рима после первоверховного Апостола Петра, от которого он, по преданию, воспринял Святое Крещение. Император Траян, негодуя на Климента, сослал его в заточение в Херсонес и заставил работать в инкерманских каменоломнях, поставлявших римлянам строительный камень. Здесь Климент, снискавший своими добродетелями любовь окружающих, с успехом проповедовал христианство.
Церковное Предание гласит, что по молитве Св. Климента в Инкермане — близ Херсонеса — чудесным образом появился источник, который в дальнейшем был превращен в крещальную купель, где принимали крещение не только жители Херсонеса и южной приморской полосы Таврики, но и кочевники из степных районов полуострова.
Предполагается, что им же были воздвигнуты в скалах и первые в Таврике христианские храмы.
Успехи и все возрастающее влияние Климента в ссылке вскоре дошли до слуха императора, который, будучи возмущен этим известием, незамедлительно отправил в Таврику одного из преданных ему лиц с тем, чтобы заставить Климента и его сподвижников отказаться от проповеди. Однако, Святой остался непоколебим. Тогда посол императора Анфидион приказал предать Епископа смерти. Зная, что христиане почитают могилы и мощи своих мучеников и опасаясь возникновения такого культа вокруг Климента, язычники решили его утопить с якорем на шее на виду у херсонесских жителей.
Согласно христианскому преданию, впоследствии ученики Климента Римского Корнилий и Фив, «собрав всю братию свою», взмолились к Господу о явлении им тела духовного наставника.
Святые Кирилл и Мефодий вносят мощи святого Климента в Рим. Фреска XI века из Базилики Святого Климента
Произошло чудо: их молитва была услышана таким образом, что море ежегодно ко дню памяти Святого отступало от берега так, что паломники по отмели свободно подходили к мощам священномученика.
В IX веке Херсонес посетили просветители славян Святые Кирилл и Мефодий. Кирилл вывез из Крыма часть мощей святого Климента и в 868 году перенёс их в Рим, где они хранятся и по сей день в базилике Сан Клементе.
Малые частицы реликвий находятся также в Севастополе и в Инкермане.
В VII веке на берега Тавриды был сослан другой Римский Первосвященник — Святой Мартин I, вызвавший недовольство византиского императора Констанция за предание его анафеме. 
Возмущенный император отправил в Рим Олимпия, приказав ему привести в Византию дерзкого Папу Римского; но так как послу это не удалось, он решил предать Мартина смерти во время литургии. Но, по преданию, подкупленный убийца не смог умертвить Римского Епископа, так как неожиданно оказался поражен слепотой.
В негодовании император послал в Рим Феодора Клеопу, поручив ему всенародно обвинить Мартина в богохульстве и измене отечеству. Однако, римляне не поверили этой клевете и остались верными своему Епископу.
Тогда враги Мартина тайно похитили его, и после долгих страданий на одном из цикладских островов он был привезен в Византию, где был приговорен к ссылке в Херсонес.
Папа Римский Мартин I скончался на третьем году пребывания в Херсонесе, оставив после себя плеяду учеников и последователей.