Церковным писателям удалось сохранить древние предания, согласно которым Крещение Кавказа началось с проповедей пяти Святых Апостолов: из них четыре Апостола были из числа 12-ти Апостолов – Святой Андрей (память 30 ноября и 30 июня), Святой Матфий (память 9 августа и 30 июня), Святой Фаддей (21 августа, память 19 и 30 июн), Святой Варфоломей (25 августа, память 11 и 30 июня).

Путешествие апостолов по Кавказу.

Святой Андрей, посещая приморские области вокруг Черного моря, когда добрался до Закавказья, то здесь начал проповедовать в прибрежных странах, находящихся на его пути, в Колхиде и Абхазии. Особенно долго он задержался в знаменитом городе Абхазии – Севастополисе (сегодняшней Искурии). Святой благовестник в горах Кавказа похоронил своего святого спутника – Симона Кананита (память 10 мая и 30 июня), и через эти горы перешел прямо к зихам, населяющих на побережье Азовского моря.

Из местных летописей известно то, что он Грузию или Иверию посетил только в западной ее части, и совсем не был в Албании и Великой Армении.
Также в Колхиде проповедовал Святой Матфий. Из свидетельств Дорофея, Епископа Тирского и Никиты Пафлагонянина видно, что Матфий был причислен к 12-ти Апостолам вместо Иуды. Он умер и захоронен в первой Эфиопии, под которой древние иногда подразумевали Колхиду. Но из свидетельств Софрония и Экумения намного определеннее видно то, что Святой Матфий проповедовал и погребен именно в Эфиопии, в которой расположены реки Гисс и Апсар, а эти реки протекают в Колхиде.

После своего путешествия у индийцев Апостол Варфоломей оставил Евангелие от Матфея на еврейском языке, и начал проповедовать в Великой Армении, и в городе Албане (Албанополисе), от него вся область именовали Албаниею. Согласно кратким сказаниям о нем III, IV и следующих веков, он потерпел мученическую смерть. Из более обстоятельных преданий об Апостоле Матфее известно то, что его проповедь имела большой успех в Великой Армении, и ему удалось привлечь к Христу самого Полимия – царя Армении со всем его двором, большинство бояр, огромное количество народа. Но его стремглав распяли на Кресте по велению Астиага — брата Царя.

Препятствия на пути христианизации.

Несмотря на то, что в Крещении Кавказа принимали участие несколько Святых Апостолов и все они имели значительные успехи, но нельзя утверждать, что в этом регионе Христианство утвердилось с того момента и было принято безоговорочно. Здесь, как и в других странах мира, оно вначале встретило очень много препятствий: со стороны языческих жрецов, угрожающих им многими лишениями, со стороны все жителей язычников, слепо преданных вере отцов, со стороны правителей и царей, с давних пор привыкших представлять себя защитниками и покровителями народной религии.

Также на Кавказе, особенно в Армении, Христианство терпело ожесточенные гонения, и даже в тех местах, в которых оно было искоренено, но все-таки оставалось в самом жалком виде. В начале IV века на Кавказе наступил новый, лучший период для христианства, когда сами владыки Иверии и Армении приняли святую веру и покровительствовали ей.