По кончине своих великих учителей – Апостолов Петра и Павла, святой Евангелист Марк снова отправился в Египет для благоустроения основанной им церкви. Много потрудился он в подвиге проповеди Христовой веры в самой Александрии. Александрия, столица Египта, была средоточием греческой образованности. Здесь было знаменитое книгохранилище, здесь процветала языческая наука; ради нее сюда стекались люди отовсюду, так что город переполнен был учеными, философами, риторами и стихотворцами. Даже иудеи, в большом количестве жившие в Александрии, увлекались языческою ученостью. Для утверждения веры Христовой и с целью противодействовать ученым язычникам и иудеям, святой Марк положил в Александрии основание христианскому огласительному училищу. В последующее время это училище сделалось средоточием христианского просвещения и прославилось тем, что из него вышли знаменитые учители Церкви, каковы: Пантен, Климент, и некоторые из отцов Церкви, каковы: Дионисий Александрийский, Григорий Чудотворец и другие.
Заботясь об устроении церковного богослужения, святой Марк составил чин литургии и передал его христианам александрийской церкви. Этот чин литургии сохранялся продолжительное время в сей церкви и в последующие века. В богослужении египетских христиан (коптов) и доселе сохранились некоторые молитвы, приписываемые Евангелисту Марку.
Благоустроив церковь александрийскую, святой Евангелист Марк в своих заботах о проповеди Христова учения не оставлял своим вниманием и усердием жителей и других городов и местностей Египта, но как крепкий и доблестный подвижник, Марк, водимый Духом Божиим, со всем усердием и ревностью всюду спешил с проповедью Христова учения. Он посетил многие внутренние страны Африки, был в Ливии, Марморике, Киренаике и в Пентаполе. Все эти страны погрязали во мраке языческого идолослужения. Всюду по городам и селениям и на распутиях были устроены кумирни, в которых были поставлены идолы и в которых совершались волхвования, провещания и чародейства. Проходя эти города и селения с проповедью Евангелия, святой Марк просвещал сердца людей, пребывавших во тьме и мраке идолослужения, светом Божественного учения, совершая в то же время между ними великие чудеса. Одним словом Божественной благодати он исцелял болящих, очищал прокаженных, изгонял нечистых и лютых духов.
И проповедь его, сопровождаемая великими и дивными чудесами, имела громадный успех. Падали кумирни, ниспровергались и разбивались идолы, люди очищались и просвещались, крестясь во имя Отца, и Сына, и Святого Духа. Всюду устроялись при Евангелисте Марке церкви Божии, и Церковь Христова процветала в египетских странах. Под действием святых слов проповеди Евангелиста Марка и под влиянием высокой чистоты и святости добродетельного жития его самого, христиане египетские, под воздействием Божественной благодати, в своих подвигах к достижению спасения проявляли столько чистоты и высоты совершенства, что их жизнь, преисполненная святости христианской добродетели, служила предметом великого удивления и похвалы со стороны даже язычников и неверующих иудеев. Евсевий, епископ Кесарии Палестинской, и Никифор (Ксанфопул) – церковные историки, сохранили в своих книгах свидетельство некоего Филона – иудейского философа, который, похваляя добродетельную жизнь христиан египетских, говорит: