По другим сказаниям, Андрей Первозванный из г. Едессы, после двух дальних путешествий, предпринял третье с несколькими спутниками в Кавказские страны, дошел до земли Иверской (Грузии), прошел Триалетскую область до р. Чороха, впадающего в Черное море близ нынешнего г. Батума, поднялся в горную Сванетию, где апостол Матвей остался устраивать молодую паству, перевалил через главный хребет в Осетию, а оттуда спустился на морской берег в Чигию и Гетию, или Джигетию (проф. А. Н. Краснов).
В 26-м томе «Сборника материалов по описанию местностей и племен Кавказа» помещена выписка из гражданских Синоксарий VIII и IX вв., хранящихся в Сионском соборе г. Тифлиса: из этой выписки видно, что апостол Андрей проповедывал Евангелие в странах приморских: Вифинии, Понте, Фракии и Скифии, посетил великий город Севастополь (Себастополис — древний Диоскурий, где ныне Сухум), потом пошел к северу в страну Джи-Гетов (Чигов-Гетов), далее в Готию и Тавроскифию (Крым); был также в г. Боспоре, где ныне Керчь. Предание, записанное Нестором, говорит, что апостол Андрей посетил Днепр, был на Киевских горах и даже в Новгороде.
Апостольская проповедь на восточных берегах Черного моря не погибла, и христианство там мало-помалу укоренилось. В IV в. на месте погребения Симона Канонита был построен храм, развалины которого возобновлены в 1875 г. (Ново-Афонский монастырь).
При Юстиниане I (527–565 гг.) христианство на Кавказе делается повсеместно господствующим; западное побережье покрывается торговыми городами греков, храмами и монастырями под прикрытием сильных крепостей. Особые архиереи стали управлять епархиями и в резиденции митрополита Пицунде, в большом торговом городе, как и Севастополь, в 551 г. строится великолепный храм Софии, Премудрости Божией, наподобие Константинопольского. Туда стекались богомольцы из ближайших и приазовских стран. Пышный расцвет христианства на этом побережье наступил в XI и XII вв., когда имеретинские цари сделались владыками и Грузии и Абхазии. Своими победами Давид Возобновитель высоко поднял знамя христианства над мусульманскими соседями и объединил страну. Даже по современным остаткам развалин можно судить, какое множество городов и храмов было на том побережье. Начавшаяся с XV в. борьба христиан с мусульманами, завладевшими даже всей Византийской Империей, привела страну в упадок. (Статья проф. А. Н. Краснова «Русская Колхида»).
Помимо греков-колонистов, христианство рано распространилось и среди туземных жителей восточного побережья Черного и Азовского морей, по низовью Дона и в Крыму, а именно среди Чигов, Черкасов, Алан, Гетов и Казахов: причем богослужебные книги были переведены на местные языки, господствующим среди которых был древний славяно-русский. О существовании этой письменности еще в языческий период мы уже говорили в VI главе; теперь же приведем лишь некоторые данные из истории церкви Приазовья. Иоанн Златоуст говорит, что Скифы, Сарматы и Индейцы (Синды Черноморские) имели уже в его время (IV в.) слово Божие на собственном их языке.
Блаженный Иероним, современник Златоуста, в послании к Летии, его духовной дочери, говорит, что «Гунны изучают псалтырь, хладная Скифия проникается пламенем истинной веры, рать (белокурых) Гетов носит с собою походные церкви».
Церковный историк Созомен Саламинский говорит о Скифах, как о народе самостоятельном, неподвластном Империи (Византийской), у которого множество не только городов, но и крепостей; что они имеют обширную и богатую столицу Томис. Он же называет Феотила, родом скифа, автокефальным архиепископом Томитанским (городов Томи и Таны) и всех прочих епархий Скифии (кн. 7, гл. 26).
Валафрид Страбон, известный толкователь Библии, живший в первой половине IX в. (был настоятелем в Рейхенау), около 844 г. пишет:
«Я слышал от верных братии, что у некоторых скифских племен, преимущественно у Томитан, и до сего времени богослужение отправляется на их собственном языке».
Герберштейн в начале XVI в. и ученый миссионер Крижанич, родом кроат, искрестивший во времена Алексея Михайловича всю Россию и даже побывавший около 15 лет в ссылке в Тобольске, положительно утверждают, в особенности последний, что Кубанские Черкасы — славяне и что богослужение у них совершается на славянском же языке. (См. главу III).
