Гораздо более богатый материал о Симоне-маге сообщают так называемые апокрифы ("отреченные" книги, не вошедшие в состав признанного церковью канона Нового завета): апокрифические деяния апостолов Петра и Павла, "прение" Петра и Симона и в особенности так называемые "Клементины" древнехристианский роман II века, описывающий, по типу греческих романов приключения, легендарное житие св. Климента, папы римского, согласно церковной легенде - ученика и преемника апостола Петра. Здесь Симон-маг изображается как неудачный соперник Симона-Петра (апостола Петра), пытающийся состязаться с ним в чудесах и вступающий с ним в прение по основным вопросам христианского вероучения. Он может воскрешать мертвых, входить в огонь, не сгорая, сбрасывать с себя цепи, менять свой облик, обращаться в животных, становиться невидимым и летать по воздуху. В Риме в присутствии императора Нерона он с помощью дьявола пытался лететь, прыгнув с высокой башни, но по слову апостола Петра низвергся на землю и разбился. Симон-маг выдавал себя за бога и мессию, его называли "великой силой божьей", язычники поклонялись ему и в Риме воздвигли ему статую. Он возил с собою женщину, которую выдавал за Елену Троянскую или Селену (Селена, по-гречески - луна), утверждая, что она - женское воплощение мировой субстанции, "премудрости божией"; на самом же деле она была его любовницей, "блудницей из города Тира". Сходный характер имеют упоминания о Симоне-маге у учителей древнехристианской церкви II-III веков (Юстина, Тертуллиана, Иринея и др.).
Как видно, Симон-маг представлен в апокрифической традиции как вероучитель одной из гностических сект, соперничавших с ранним христианством: гностики пытались примирить христианство с язычеством путем аллегорического истолкования античных и христианских мифов в духе мистического неоплатонизма, широко распространенного в Риме в период упадка рабовладельческого общества.
Легенда о Симоне-маге была хорошо известна в средние века, в частности и в Германии. Она вошла в "Императорскую хронику" ("Kaiserchronik"), немецкую поэму середины XII века, имевшую широкое распространение и влияние, была знакома и протестантским богословам, и демонологам XVI века {См., например: Andreas Hondorff. Prompluarinm exemplorum. 1568, л. 33а (ср.: Реtsсh. Faustbuch, стр. 211-212). Ср.: Тексты. 1, 19 и прим.}. Сравнение Фауста с Симоном-магом встречается у Меланхтона (Тексты, I, 13 и 15), Мейгериуса (Тексты, I, 30 и прим.) и в самой народной книге о Фаусте (гл. 52). Можно думать, что рассказ Меланхтона о неудачном полете Фауста при дворе императора и эпизод с Еленой в народной книге непосредственно связаны с этим сказанием. Возможно также, что фигура "гомункулуса", искусственного создания Вагнера во II части "Фауста", подсказана была Гете традицией, восходящей к "Клементинам", где Симон-маг вместе с Еленой в соответствии с гностическими представлениями создает человека путем магической трансформации элементов.
Ко временам раннего христианства относится легенда о святых Киприане и Юстине из Антиохии в Сирии, в которой изображается столкновение между языческой (демонической) и христианской (церковной) магией на фоне еще не законченной борьбы между христианством и язычеством, оставшимся еще государственной религией Римской империи {См.: Theodor Zahn. Cyprian von Antiochien und die deutsche Faustsage. Erlangen. 1882. - L. Radermacher. Griechische Quellen zut Faustsage. Sitzungsberichte der Wiener Akademie der Wissenschaften, philos.-histor. Klasse. Bd. 206, Abb. 4, 1927. стр. 5-41 (Cyprianus und Justina). - Faligan. стр. XVIII. - Dedeуan, стр. 146-148. Kuno Fischer, стр. 227-234. - Белецкий. V, стр. 62-63, - П. Безобразов, Византийские сказания. Юрьев, 1917, стр. 223-226.}. Согласно церковному преданию, Киприан и Юстина претерпели мученическую кончину при императоре Диоклетиане, т. е. в середине III века, хотя существуют и другие, столь я;е легендарные хронологические приурочения (при Клавдии, Деции и др.). Жития этих мучеников сохранились в разных версиях на греческом и латинском языках. О Киприане упоминает уже Григорий Назианзин в своих проповедях (гомилиях) в 379 году, латинский христианский поэт Пруденций (около 400 года) и др.; в середине V века житие Киприана и Юстины было обработано по-гречески в стихотворной форме императрицей Евдокией, женой императора Феодосия II.
Язычница Юстина, дочь жреца из Антиохии. вместе со своими родителями приняла христианство и в духе аскетизма ранней христианской церкви дала обет девственности. Дьявол, чтобы соблазнить ее, внушил к ней страсть знатному юноше Аглаиду. Отвергнутый Юстнной, Аглаид обратился к языческому магу Киприану, который за вознаграждение обещал помочь ему дьявольскими чарами. Но попытки дьявола обольстить Юстину неизменно терпели поражение: магической силой крестного знамения Юстина отгоняет искусителя. Дьявол вынужден признать свое бессилие перед крестом. Тогда Киприан, уверовав в силу Христа, сам обращается в христианство и вместе с Юстиной претерпевает мученическую смерть.