Але християнство з’явилося не на пустому місці. Значну роль у його становленні відіграв релігійний синкретизм (у філософії — поєднання різнорідних, суперечливих, несумісних переконань), який живив християнську ідеологію, що поступово складалася. У перші століття нашої ери в Херсонесі зберігався грецький божественний пантеон.
Але нарівні з традиційними грецькими культами у місті набули поширення нові релігійні течії. Внаслідок традицій та через консервативність грецької частини населення, старі греко-римські боги не сходять з арени, а набувають багатьох рис нових християнських божеств. У Херсонесі досить добре простежується потяг до язичницького монотеїзму (єдинобожжя), що також було наслідком релігійних шукань в ту ж епоху.
Про проникнення християнства у Херсонес ми маємо досить значну кількість джерел, які, однак, не завжди дослідниками інтерпретувалися правильно. Це, насамперед, поховання, де було знайдено речі з християнською символікою. Але їх у IV — V століттях небагато і вони істотно не відрізняються від багатьох місцевих язичницьких поховань. Минулого століття тут було відкрито вісім склепів iз християнським розписом, які відносили до IV — V століть і розглядали як один iз найнадійніших показників раннього проникнення християнства. Але зараз встановлено, що склепи були розписані та стали об’єктами культу не раніше VI — VII століть, коли їх почали пов’язувати з легендами про перших християнських мучеників.
Відсутність у похованнях значної кількості речей з християнськими символами свідчить про наявність у цьому полісі досить тривалого перехідного періоду від язичництва до християнства. Для нього була характерною язичницько-християнська символіка та відсутність типово християнських рис у похоронному обряді. Адже християнський похоронний обряд не було ще чітко регламентовано, та й сама нова релігія переживала лише період становлення. Вона пристосовувала до своїх вимог багато що не тільки з обрядової античної практики, але також і частково — уявлення про потойбічний світ та безсмертя душі.
Про час християнізації населення цього регіону свідчать і агіографічні твори. Згідно з відомим житієм святого апостола Андрія, вважалося, що вже у I —II ст. Херсонес був християнським містом. Але легенда про подорож апостола Андрія була запозичена з апокрифів II — III ст., де йшлося про його місіонерську діяльність у Скіфії.
Перші згадки про приїзд апостола Андрія в Херсонес відносяться до кінця VIII — IX ст. Легенда про заслання та мученицьку смерть римського єпископа Климента у ці краї також з’явилася пізніше. Вона була пов’язана з Херсонесом тільки після того, як у IX ст. Костянтин Філософ, видатний слов’янський філософ, «відкрив» у Херсонесі його мощі, частина яких була вивезена князем Володимиром та зберігалася у Києві в Десятинній церкві.
Більш складним для дослідників є питання про вірогідність «Житія святих єпископів херсонеських». Вони розповідають про приїзд у місто в період правління Діоклетіана перших християнських місіонерів, яких направив єрусалимський єпископ, і про їхню смерть саме тут від рук язичників.
Але беззастережно приймати ці дані не можна. До III Вселенського собору (431 р.) єрусалимська церква не відігравала провідної ролі у християнському світі і не могла направляти своїх місіонерів у Херсонес.
Є у «Житіях» також і розповідь про хрещення. Імператор Костянтин Великий у 325 р. на прохання деяких «вірних» церквi послав у Херсонес єпископа Капітона у супроводі військового загону. Але жителі не захотіли приймати нової віри. Однак після того, як Капітон увійшов у вапняновипалювальну піч і вийшов звідти неушкодженим, вони прийняли нову віру. Про це негайно повідомили імператору Константину, який перебував у Нікеї (Мала Азія) на церковному соборі.
Історична основа цієї розповіді викликає, проте, сумніви. «Житія» були написані не раніше VII ст., тобто вони створені пізніше описаних подій і відображають спробу церкви створити свою власну героїчну історію, автори якої розглядали час з 303 до 311 р., як «еру мучеництва».
Боротьба, яка відбувалася між прихильниками та противниками християнства, мученицька смерть перших місіонерів і, нарешті, «чудо» Капітона — всі ці події повинні були закласти непохитну віру в церковну організацію, освячену самим імператором Константином Великим, з іменем якого і пов’язувалася остаточна перемога християнства в Римській імперії. Чи не тому над вапняновипалювальною піччю в VII ст. було зведено храм-пам’ятник. Таким же цілям слугував і християнський розпис склепів, у сюжетах якого провідне місце займали вінки — символ мучеництва, а також і монограми Христа. Хронологічно ці події співпадають iз пожвавленням церковного будівництва в Херсонесі у VI — VII ст.
Показником раннього проникнення християнства, як вважалося, є підпис херсонеського єпископа під документами I Вселенського собору (325 р.). Але ті списки, де він є, походять від оригіналу кінця VII — VIII ст. У більш ранніх списках імені єпископа Херсонеса ще немає. Про херсонеського єпископа можна говорити тільки щодо II Вселенського собору (381 р.).
Присутність єпископа на II Вселенському соборі, археологічні пам’ятки та фрагментована скульптура IV — V ст. свідчать, що в цей час у Херсонесі вже існувала невелика християнська община, але ще не було спеціального некрополя. Тільки наприкінці V — початку VI ст. на південному сході від міста з’являється каплиця, навколо якої починають зводити поховання перших християн. Пізніше на її місці було побудовано заміський храм Богородиці Влахернської, який, мабуть, виник на місці поховання засланного сюди римського Папи Мартіна I (середина VII ст.).
Наведені дані свідчать про довгий та складний шлях становлення у Херсонесі нової релігії. Широка християнізація місцевого населення почалася тут не раніше VI ст. і була пов’язана з активізацією візантійської політики у Тавриці в період правління могутнього імператора Юстиніана I (527 — 565 рр.).
До цього часу відносяться такі події, як перепланування кварталів, зумовлене храмовим будівництвом, канонізація мучеників, склепи з християнським розписом, поява християнських похоронних комплексів, а також і перші надгробки із зображенням хрестів.
Але остаточна перемога християнства в Херсонесі, як і в інших районах Візантійської імперії, була досягнута тільки в епоху раннього середньовіччя. І незважаючи на те, що Херсонес (або візантійський Херсон) був основним форпостом християнської церкви у Північному Причорномор’ї, до XIII ст. у світогляді його населення зберігалися пережитки язичницьких вірувань.
