Распространение христианского вероучения среди алан, согласно церковной традиции, начинается в 40 г. н. э. с проповеднической деятельности апостола Андрея, охватившей прилегающие к Черному морю районы. Различной полноты сведения о ней появляются с III в. в трудах Оригена, Евсевия Памфила, епископа Тирского св. Дорофея, епископа Епифания Кипрского, епископа Ипполита, Сафрония, Праксейса, Никиты Давида Пафлагонского, Арсения Керкирского, патриарха Никифора Каллиста, иерусалимского иеромонаха Епифания и др. Последний сам прошел по легендарным местам проповеди и составил «Хождения Андрея», которые явились сводом существовавших до него преданий и легли в основу грузинского и славянского вариантов. Сокращенное и несколько переделанное изложение труда Епифания было произведено Симеоном Метафрастом и вошло в греческие Минеи. О путешествии св. Андрея повествуют русские православные Четьи Минеи. О давнем миссионерстве свидетельствует коптская литература. В Грузии сообщения о нем отмечены в «Картлис цховреба» и у Георгия Мтацминдели. У абхазов и осетин сохранились предания о посещении апостолом их земель. Подобные легенды бытовали по всему побережью Черного моря, во многих городах и местностях стояли церкви в честь апостола, хранились иконы с его изображением.