Хотя почитание Елисея установилось, по-видимому, лишь в VI–VII вв., он стал подлинным символом албанского христианства: местная церковь неизменно чтила его память, Житие Елисея включено в армянский синаксарь. В той же восточной части будущего Албанского марзпанства проповедовал и другой ученик апостола Фаддея, Дади, над могилой которого во второй половине I в. был основан монастырь Дадиванк. «Второе крещение» Кавказской Албании имело место при Григории Просветителе в начале IV в. По одной из редакций его Жития, когда святой направлял иереев и епископов в соседние страны, Албания досталась благочестивому епископу Фоме из города Саталы (Малая Армения). Согласно армянским источникам, в 330 гг. внук Григория Просветителя Григорис, рукоположённый во «епископа Иверии и Алуанка», прибыл в Албанию из Армении, «обновил» храмы, вёл проповедь среди местного населения и также принял мученическую смерть среди мазкутов (около 338 г.); его гробница находится в Амарасе. К этому же времени относятся сообщения грузинских источников о крещении Эрети св. Нино (Нины), которой новообращённый царь Картли Мириан придал в сопровождение войско во главе с эриставом. В документах Соборов персидской Церкви Востока Арран (Кавказская Албания) упоминается среди епархий, подчинённых патриарху-католикосу с резиденцией в Селевкии-Ктесифоне, но это подчинение было, видимо, чисто номинальным. Возобновление проповеди христианства среди народов Кавказской Албании около 420 г. связано с именем Месропа Маштоца и Даниеля, которым источники приписывают создание албанского алфавита. Судя по материалам первого Двинского собора (506 г.), албанский являлся официальным языком церкви. Армянский католикос Бабген писал о христианстве кавказских стран к своим персидским единоверцам: «У нас такая вера, как мы писали вам ранее, в согласии с грузинами и албанами, каждый на своём языке». Предположение ряда учёных о существовании литургических памятников на албанском языке нашло подтверждение: более сотни страниц албанских текстов, очевидно богослужебного назначения, были обнаружены недавно на Синае в грузинском палимпсесте. С VII в. интенсифицируется процесс арменизации Албанской церкви, и в более позднюю эпоху богослужение в ней велось на армянском языке. Впрочем, албанская письменность долгое время продолжает использоваться в левобережной части (раскопки комплекса у Мингечаура выявили как албанские, так и армянские надписи середины VII в.). Первым албанским правителем, принявшим христианство, был царь Урнайр, крестившийся в Армении около 370 г. В конце V в. албанский царь Вачаган III Благочестивый, в союзе с Арменией и Грузией выступивший против попытки Сасанидов запретить христианство, торжественно принял крещение и объявил христианство официальной религией, приняв суровые меры против язычников (в стране был распространён и зороастризм вплоть до Х в.).