B VIII, IX и последующих столетиях накопившийся веками материал в форме апокрифических и церковных сказаний, кратких известий и посеянных всюду теми и другими местных преданий, послужил источником к составлению новых «деяний», «похвал» и «житий» апостолов. Здесь миссионерская деятельность ап. Андрея распадается на целых три проповеднических путешествия, скопированных с путешествий ап. Павла, причем Первозванный апостол уже с полной определенностью проводится через Скифию европейскую и по северному и по западному побережью Черного моря проходит до Византии, где поставляет первого епископа для этого города — Стахия. Из повествований последнего рода следует отметить рассказ монаха Епифания [3], так как в нем есть некоторые элементы, вошедшие впоследствии в русское сказание. Епифаний жил в конце VIII и нач. IX вв., когда жгучим вопросом современности был вопрос об иконах. Под влиянием этого церковного интереса, Епифаний, как и некоторые другие лица того времени, предпринял своего рода учено-археологическое путешествие по прибрежным странам Евксинского Понта, с целью изучить местные памятники и предания, касающиеся внешнего богопочитания во времена апостолов. Поэтому в своем повествовании об ап. Андрее он тщательно отметил все священные изображения, жертвенники, храмы и кресты, ведущие свое начало, по рассказам местных жителей, от времени проповеди у них названного ученика Христова. Здесь, между прочим, не раз упоминается о «железном жезле с изображением животворящего креста, на который апостол всегда опирался». Неподалеку от Никеи в Вифинии «блаженный ап. Андрей, низвергнув гнусную статую Артемиды, поставил там животворящее изображение спасительного Креста». Далее к востоку, в Пафлагонии «он избрал место молитвы, удобное для устроения жертвенника, и освятил его, воздвигнув знамение животворящего креста». Вот откуда ведут свое начало и крест и жезл, фигурирующие в двух версиях русского сказания. У монаха Епифания [4], ап. Андрей из кавказских стран, не обходя Меотического залива (Азовское море), через пролив (Керченский), приходит прямо в Боспор (Керчь); отсюда проходит в крымские города Феодосию и Херсонес; далее плывет морем на Синоп и возвращается в Византию. Гораздо смелее выражаются позднейшие греки и шире представляют себе район миссионерской деятельности ап. Андрея на севере от Черного моря. Никита Давид Пафлагонский (кон. IX и нач. X в.), известный биограф патр. Игнатия, составил ряд риторических похвальных речей в честь апостолов. В похвале ап. Андрею [5] он выражается так: «Получив в удел север, ты обходил Иверов и Сарматов, Тавров и Скифов, всякую страну и город, которые лежат на севере Евксинского Понта и которые расположены на его юге» (соl. 64). «Итак, обняв благовестием все страны севера и всю прибрежную область Понта… он приблизился к оной славной Византии» (соl. 68). Под таким углом зрения и терминология древних апокрифов теперь с решительностью применялась к пространствам южной России. Еще у хрониста Иоанна Малалы (VI в.) имя мирмидонян («антропофагов» апокрифов) прилагается к болгарам, когда они обитали у Меотики, т. е. у Азовского моря. Для Льва Диакона (X в.) Мирмидония находилась там же, и мирмидоняне уже считались предками руссов, а владения руссов около Азовского моря наз. Мирмидонией. «Во всяком случае», говорит В. Г. Василевский, «не подлежит ни малейшему сомнению, что в XI в. имя мирмидонян, наряду с другими, унаследованными от классической древности названиями, служило для обозначения русских. Таким образом, в византийском предании и литературе XI в. существовало очень много данных для составления хождения ап. Андрея по русской земле.