Двенадцать учеников Иисуса разделили между собой страны, куда они должны были нести евангельскую проповедь, обращая язычников ко Христу. Святому Андрею выпали по жребию обширные земли Вифинии и Пропонтиды с городами Халкидон и Византия, также земли Фракии и Македонии, простирающиеся до Чёрного моря и Дуная, кроме того, земли Скифии и Фессалии, Эллады и Ахайи, города Амине, Трапезунд, Ираклия и Амастрида. Святой Андрей прошел эти города и страны, неся язычникам евангельскую проповедь. Первым поприщем его апостольского служения стало побережье Чёрного моря, которое в те времена называли Эвксинским Понтом (Гостеприимным морем).
Апостол Андрей проповедовал в Малой Азии, прародине хеттов-скифов, где его жестоко пытали и чуть не убили в Синопе язычники, основал епископию в городе Византии (будущем Константинополе), прошел все северное побережье Черного моря от Босфора до Абхазии, посетил города Феодосию и Херсонес.
Древнерусские источники, считают, что путь апостола Андрея пролегал значительно дальше на север. Повесть временных лет, начиная с общего с другими источниками утверждения о служении апостола в Причерноморье: «А Днепр втечет в Понетьское море жерелом; еже море словет Руское, по немуже учил святый Оньдрей, брат Петров» (Стлб. 7), — далее рассказывает о том, что по прибытии в Корсунь Андрей узнал, что неподалеку находится устье Днепра, и, решив отправиться в Рим, поднялся вверх по Днепру. Остановившись на ночлег на холмах, на которых впоследствии был построен Киев, апостол, по утверждению летописца, сказал бывшим с ним ученикам:
«Видите ли горы сия? Яко на сих горах возсияет благодать Божия, имать град великий быти и церкви многи Бог въздвигнути имать».
Апостол поднялся на горы, благословил их и водрузил крест. В XIII в. на месте, где это, по преданию, произошло, была сооружена церковь во имя Воздвижения Честного Креста, замененная в середине XVIII столетия храмом архитектора Растрелли в честь самого Первозванного апостола.
Различные средневековые источники сообщают о дальнейшем пути святого Андрея в Новгород, где он воздвигнул крест около нынешнего села Грузино на берегу Волхова, к Ладожскому озеру и далее до острова Валаам, где он установил каменный крест. Оттуда апостол, как считается, направился в Рим через Польшу (польское средневековое предание о принятии крещения от Андрея Первозванного также существует).
«В древнейшей рукописи «Оповедь», хранившейся в монастырской библиотеке Валаама, об этих событиях сообщалось: «Св. Андреи от Иерусалима прошел Голядь, Косог, Родень, Скеф, Скиф и Словен смежных лугами, достиг Смоленска, и ополчений Скоф и Славянска Великого, и Ладогу оставя, в ладью сев, в Бурное вращающееся озеро на Валаам пошел, крестя повсюду и поставлял по всем местам кресты каменные. Ученики же его Сила, Фирс, Елисеи, Лукослав{385}
, Иосиф и Косма повсюду сделали ограды и все посадники доезжали от Словенска и Смоленска, и многие жрецы окрестились и капища Перуна и Велеса разрушили и уничтожили». О пребывании св. Андрея на Валааме говорит и другой па мятник древности: «Вселетник» киевского митрополита Илариона 1051 года, оригинал которого утерян. Во «Вселетнике» говорилось: «Ноября 30–го св. ап. Всехвального Андрея Первовозванного и Церкви поборника восхвалим: зане, якоже древ[не] тому прийти в Киев, Смоленск, Новгород, Друзино (Грузино) и Валаамо»{386}.Из той же «Оповеди» известно, что каменный крест, установленный святым Андреем Первозванным, сохранялся на Валааме до времени преподобного Сергия Валаамского.
Митрополит Макарий (Булгаков) замечает по этому поводу: «Предание о благовестии святого апостола Андрея даже во внутреннейших областях нашего отечества не заключает в себе ничего невероятного, и нет основания отвергать его безусловно или принимать за одну идею».
Историки, наоборот, считают, что летописные рассказы о крещении славяно-русов апостолом Андреем носят мифический характер. Скепсис и ирония по отношению к этому преданию проникли даже в ученые клерикальные круги. Профессор Московской духовной академии Е. Е. Голубинский (н. XX века) посвятил целый раздел своей фундаментальной «Истории русской церкви» (т. I. M., 1901) разбору летописного рассказа о «хождении» апостола Андрея в Россию, назвал его «легендой» и «крайне несообразным вымыслом», так как этот рассказ «заставляет апостола идти путем, который не только в 50 раз длиннее обыкновенного, но который в его время был совершенно неизвестен», направляет его в «неведомую пустыню», где апостол «не мог иметь никакой надежды утвердить сколько-нибудь прочным образом христианство … Для чего же предпринимал бы он в нее путешествие? Не для того же в самом деле, чтобы ставить кресты на необитаемых горах или наблюдать такие обычаи, как паренье в банях…» — ехидно вопрошает этот ученый богослов.