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