Начало христианской проповеди на землях Северного Причерноморья, Поднепровья и Тавриды было положено ещё в I веке учеником Иисуса Христа апостолом Андреем Первозванным. Апостол, проповедуя Евангелие, прошёл большой путь от Греции до славянских земель, где спустя столетия возникнут города Киев и Новгород.
Исследователи признают вполне достоверным тот факт, что апостол Андрей проповедовал в Северном Причерноморье. Тому есть документальные свидетельства: церковный историк IV века Евсевий Кесарийский сообщает, что Андрей Первозванный получил по жребию для проповеди Скифию.
Преподобный Нестор Летописец в «Повести временных лет» пишет о проповеди святого Андрея на месте будущего Киева. Различные средневековые источники сообщают о дальнейшем пути апостола в Новгород, где он воздвигнул крест на берегу Волхова, к Ладожскому озеру и далее до острова Валаам, где он будто бы установил каменный крест и истребил капища богов Велеса и Перуна, обратив в христианство языческих жрецов.
Летописное известие о проповеди апостола Андрея на земле, где позже возникнет Русское государство, для нас чрезвычайно дорого. Через это предание освящается наша Русская земля, а несомненный факт миссионерской деятельности святого Андрея Первозванного в Тавриде, в частности Херсонесе, лишь укрепляет историческую духовную связь с местом начала крещения Руси, хоть и несколько веков спустя.
В Крыму апостол Андрей посетил приморский город Понта Эвксинского Пантикапей (Керчь), где успешной проповедью и чудесами обратил многих в христианство. Оттуда, следуя вдоль южного поморья Тавриды, пришёл в Феодосию. Сборник житий «Ангелы апокалипсиса» свидетельствует, что лишь малое число жителей этого портового города уверовало в Иисуса Христа.
Мы можем лишь предположить в точности маршрут святого, но, скорее всего, далее на его пути были Судак, Алушта (в окрестностях Алушты есть целебный источник, у которого, по преданию, Андрей беседовал с местными жителями, источник назван с древних времён его именем). Далее последовала проповедь на Медведь-горе (Аю-Даге), в те времена она была населена. После — Гурзуф, окрестности современной Ялты, Инкерман и, наконец, Херсонес, где, как говорят летописи, «апостол провёл много времени».
В Херсонесе «обитали люди грубые и неверные, но склонные к христианству». Апостол пробыл у них долгое время и многих обратил к Иисусу Христу. Причём Херсонес святой Андрей посетит ещё раз, уже после странствий по славянским землям. О путешествии Андрея Первозванного в Херсонес свидетельствует «Степенная книга» — один из крупнейших средневековых памятников литературы, повествующий о русской истории с древнейших времён до XVI века. Именно в этом источнике говорится о том, что апостол Андрей благословил Чёрное море. Во время проповеди он стоял на большом камне, на котором, как на воске, отпечатались его ступни и вода из этих отпечатков (на Херсонесе же) имеет целебную силу.
По преданию, на мысе Фиолент, где сейчас установлен памятник апостолу, также произошло одно из чудес. Святой жил и молился уединённо — в одном из гротов. Однажды, придя в пещеру Дианы, он увидел, что статуи богов Артемиды и Аполлона были разрушены, то есть молитва достигла цели. Капище опустело. Руины языческого храма Дианы описывал в своём крымском путешествии А. С. Пушкин.
Византийский историк девятого века Никита Пафлагонский в «Похвальном слове к апостолу Андрею» писал: «Получив в удел север, ты обходил и сарматов, и тавров, и скифов». И плодотворно! Счёт неофитов, обращённых в истинную веру, уже шёл на тысячи.
Через 30 лет после апостола Андрея в Крым прибыл священномученик Климент Римский. Святой был сослан в Инкерман за проповедь о Христе. По его свидетельству, благодаря слову Первозванного апостола, только в этом поселении он встретил общину из двух тысяч христиан.
Не менее важно и то, что в составе канонической территории Русской Православной Церкви и сегодня пребывают земли, где христианство бесспорно появилось уже в первые века своей истории: Крым, Северное Причерноморье, часть Кавказа. Археологические находки, сделанные в Херсонесе, Керчи и многих других греко-римских поселениях Крыма, Приазовья и Новороссии, свидетельствуют о том, что христианство там распространилось уже в I–III веках.
Сегодня многое в Крыму напоминает о святом апостоле: и топонимы причерноморских поселений, и храмы, освящённые в его честь, и памятники (в Севастополе их три!), и Андреевские флаги на кораблях Черноморского флота… А самое главное, крещение Руси, которое произошло при святом князе Владимире, и взяло своё начало из Корсуни — Херсонеса, отнюдь не было первым знакомством Руси с христианством. К этому времени уже была подготовлена почва для скорого распространения Православия среди русского народа. В этом аспекте переоценить значение миссионерской деятельности, слова проповеди святого апостола Андрея Первозванного в наших землях, в том числе Крыму, невозможно.