Вскоре после апостольского Собора Павел предпринял второе великое путешествие с проповедью Евангелия, во время которого, пройдя Сирию, Киликию и Галатию, вследствие видения (Деян. гл. 16), перешел в Европу и основал церковь в Филиппах (Македонии). В 52 г. он проповедовал в Солуни, основал церкви в Верии и Афинах, прибыл в Коринф. Там он работал у христианина из иудеев, Акилы, ушедшего из Рима, согласно указу того года имп. Клавдия об изгнании иудеев из Рима. Акила и жена его Прискилла сопровождали потом ап. Павла до Рима. Всюду он совершал богослужения в домах христиан. К 53-му году относятся два послания ап. Павла к Солунянам. Еп. Арсений пишет: "Около сего же времени, может быть, спутник ап. Павла, Лука, написал в Коринфе Евангелие, известное под его именем".
В 54 г. ап. Павел к празднику Пятидесятницы прибыл в Иерусалим, затем пошел в Антиохию, где прожил недолго. Оттуда предпринял он третье проповедническое путешествие: прошел Киликию, Фригию и Галатию и к зиме прибыл в Ефес. Там он принял в церковь учеников Иоанна Крестителя (Деян. гл. 19). В Ефесе он провёл более двух лет. Оттуда же он написал в 55 г. послание к Галатам и в 56 г. первое послание к Коринфянам. В 57 г. он посещает церкви, основанные им в Македонии, и пишет второе послание к Коринфянам. Три месяца живет он в Коринфе (еп. Арсений).
Ап. Петр, оставшийся в Антиохии после Павла, завершил устройство тамошней церкви и примерно в это же время поставил ей епископа Еводия. Затем он проповедовал в области антиохийской, в Понте, Галатии, Каппадокии и Вифинии. Наконец, ап. Петр отправился благовествовать иудеям вавилонским. В то же время ап. Марк, родственник Варнавы, по поручению ап. Петра отправился в Египет с проповедью Евангелия. Для основанной в Александрии церкви он поставил первого епископа Аниана.
В 58 г. ап. Павел, предполагая посетить Рим, составил послание к римской церкви, в которой большинство христиан составляли обращенные язычники. По этому поводу еп. Арсений пишет: "Из того, что ап. Павел нигде в послании не упоминает о предварительном благовестии апостольском в Риме, в ряду многочисленных приветствий разным лицам (гл. 16) также не упоминает ни о ком из апостолов, равно и принимая во внимание, что ап. Павел принял себе за правило действовать независимо и самостоятельно и не вмешиваться в область других апостолов (Рим. 15:20-21; 2 Кор. 10:16), следует заключить, что до того никто из апостолов не благовествовал в Риме, что римская церковь образовалось, подобно антиохийской, сначала из апостольских учеников и членов церкви иерусалимской, потом, после изгнания из Рима евреев и в том числе христиан из евреев, усилилась обращенными преимущественно через учеников ап. Павла язычниками, которых указ Клавдия не касался. Во время написания послания римская церковь была уже многочисленна и значительна, хотя во главе её не было ещё епископа".
После Коринфа ап. Павел провел Пасху в Филиппах и на праздник Пятидесятницы прибыл в Иерусалим. По наветам иудеев он, как "возмутитель", был взят под стражу и отправлен в Кесарию к прокуратору римскому. Там он из-за происков иудеев и несправедливости прокуратора Феликса два года пробыл в узах.
В 61 г. ап. Павел отверг предложение нового прокуратора Феста судиться в синедрионе и на правах римского гражданина потребовал суда кесарева. Поэтому он был отправлен в Рим, куда и прибыл к концу марта того же года. Находясь там под военным надзором, он жил в частном доме, как не совершивший большого проступка. О своей проповеди в Риме он упоминает в послании к Филиппийцам, указывая, что эта проповедь достигла и дома кесарева. Сопутствовавший Павлу Евангелист Лука в Риме закончил свою книгу "Деяний апостолов". Тогда же по предложению еп. Арсения он рукоположил и первого епископа римской церкви, св. Лина, своего ученика. Из Рима ап. Павел поддерживал общение со всеми основанными им Церквами в Греции и Малой Азии, а христианам филиппийским, колосским и ефесским писал и послания. Из Рима же писал он к Филимону, гражданину колосскому (еп. Арсений).
В 62 г. первосвященник Анан, воспользовавшись смертью Феста и отсутствием нового прокуратора, воздвиг гонение на еп. Иакова Иерусалимского. Он требовал от него провозглашения с кровли храма о заблуждении тех, кто признают Иисуса Сыном Божиим. Иаков же произнес исповедание веры. Разъярённые книжники и фарисеи сбросили апостола с крыши храма, и один, заметив, что он дышит, довершил мученичество, раздробив ему голову. Царь Агриппа за этот самовольный поступок лишил Анана первосвященства. Имеется послание ап. Иакова "двенадцати коленам, находящимся в рассеянии", написанное, по мнению еп. Арсения, вскоре после Апостольского собора. Преемником его стал св. Симеон, сын Клеопы, брата Иосифа Обручника.
В 63 г. ап. Павел был освобожден благодаря недоказанности обвинений против него, одобрительным отзывам о нем римских правителей Иудеи и его собственной беспорочной жизни. Тогда он (по предположению еп. Арсения), путешествовал в Испанию и из Рима отправил туда семь благовестников, которые и учредили там первые епископские кафедры. После этого ап. Павел проповедовал на о. Крите, где оставил ученика своего Тита, был в Ефесе, поставив епископом Тимофея. Находясь в Македонии, он (в 64 или 65 гг.). отправил первое послание к Тимофею и одно к Титу. Примерно в это же время апп. Иасон и Сосипатр положили основание Церкви в Коркире, нынешнем Корфу.
В 65 г. ап. Павел, оставив Македонию, снова посещает азийские церкви и приходит в Коринф. Туда же прибыл с Востока ап. Пётр, и они вдвоём отправились в Италию для утешения и ободрения гонимых при императоре Нероне христиан. Из Рима ап. Павел отправил своё послание к Евреям. Лжебратия об этом донесли, и апостолы были заключены в темницу в конце того года или в начале следующего. В 67 г., после нескольких месяцев пребывания в темнице, ап. Павел был усечён мечом.
В своей "Истории христианской Церкви" Евграф Смирнов пишет: "Одно перечисление путешествий этого великого апостола, которые он совершал почти постоянно после своего обращения в продолжение тридцати лет, говорит уже о том, что он был одним из ревностнейших и самых неутомимых проповедников христианства. Глубокое убеждение в истинности проповедуемого им учения, ясное понимание христианских истин, спокойное мужество среди всевозможных опасностей, необыкновенное знание человеческого сердца и от природы увлекательная сила красноречия при благодатных дарах Св. Духа содействовали его необыкновенным успехам. Множество христианских общин на пространстве почти всей Римской империи от востока до запада считают его своим основателем. Неутомимый проповедник своей апостольской ревностью возбуждал к такой же проповеди и других. Он образовал сонм проповедников христианства, которые в Деяниях апостольских и посланиях ап. Павла поименно упоминаются под названием сотрудников и спутников его".
Труды ап. Петра и прочих апостолов
Ап. Пётр принял на себя труд распространять христианство между иудеями. Из язычников он обратил в Иерусалиме по особенному внушению Божию целое языческое семейство. В 44 г., когда ему угрожала смерть от Ирода Агриппы, он, освобождённый ангелом из темницы, на долгое время оставил Иерусалим, проповедуя в соседних провинциях, особенно же, в Антиохии. Ап. Пётр в 51 г. присутствовал на Апостольском соборе. Считается, что после собора, он, посетив Антиохию, проповедовал иудеям рассеяния в Понте, Галатии, Каппадокии, Асии и Вифинии, к которым писал своё первое послание. Затем ап. Пётр со своим учеником Марком проповедовал в Вавилоне Египетском, и в Александрии ап. Марк основал церковь. Посетил ап. Пётр и Коринф после того, как ап. Павел основал там церковь.
В 67 г. ап. Пётр прибыл в Рим, где, по свидетельству Тертуллиана, рукоположил третьего римского епископа Климента. В 66-м или в начале 67-го года ап. Пётр был заключен в темницу и через несколько месяцев распят на кресте, вниз головой, так как считал себя недостойным быть распятым, как Спаситель.
Ап. Андрей проповедовал в Каппадокии, Галатии, Вифинии, вообще по восточным и северным берегам Черного моря и в Скифии. По преданию он был на месте будущего Киева. Мученическую смерть апостол претерпел в Патрасе, в Ахаии. В Византии он поставил первым епископом св. Стахия, и таким образом от него ведёт свое начало константинопольская иерархия.