В 63 г. ап. Павел был освобожден благодаря недоказанности обвинений против него, одобрительным отзывам о нем римских правителей Иудеи и его собственной беспорочной жизни. Тогда он (по предположению еп. Арсения), путешествовал в Испанию и из Рима отправил туда семь благовестников, которые и учредили там первые епископские кафедры. После этого ап. Павел проповедовал на о. Крите, где оставил ученика своего Тита, был в Ефесе, поставив епископом Тимофея. Находясь в Македонии, он (в 64 или 65 гг.). отправил первое послание к Тимофею и одно к Титу. Примерно в это же время апп. Иасон и Сосипатр положили основание Церкви в Коркире, нынешнем Корфу.
В 65 г. ап. Павел, оставив Македонию, снова посещает азийские церкви и приходит в Коринф. Туда же прибыл с Востока ап. Пётр, и они вдвоём отправились в Италию для утешения и ободрения гонимых при императоре Нероне христиан. Из Рима ап. Павел отправил своё послание к Евреям. Лжебратия об этом донесли, и апостолы были заключены в темницу в конце того года или в начале следующего. В 67 г., после нескольких месяцев пребывания в темнице, ап. Павел был усечён мечом.
В своей "Истории христианской Церкви" Евграф Смирнов пишет: "Одно перечисление путешествий этого великого апостола, которые он совершал почти постоянно после своего обращения в продолжение тридцати лет, говорит уже о том, что он был одним из ревностнейших и самых неутомимых проповедников христианства. Глубокое убеждение в истинности проповедуемого им учения, ясное понимание христианских истин, спокойное мужество среди всевозможных опасностей, необыкновенное знание человеческого сердца и от природы увлекательная сила красноречия при благодатных дарах Св. Духа содействовали его необыкновенным успехам. Множество христианских общин на пространстве почти всей Римской империи от востока до запада считают его своим основателем. Неутомимый проповедник своей апостольской ревностью возбуждал к такой же проповеди и других. Он образовал сонм проповедников христианства, которые в Деяниях апостольских и посланиях ап. Павла поименно упоминаются под названием сотрудников и спутников его".
Труды ап. Петра и прочих апостолов
Ап. Пётр принял на себя труд распространять христианство между иудеями. Из язычников он обратил в Иерусалиме по особенному внушению Божию целое языческое семейство. В 44 г., когда ему угрожала смерть от Ирода Агриппы, он, освобождённый ангелом из темницы, на долгое время оставил Иерусалим, проповедуя в соседних провинциях, особенно же, в Антиохии. Ап. Пётр в 51 г. присутствовал на Апостольском соборе. Считается, что после собора, он, посетив Антиохию, проповедовал иудеям рассеяния в Понте, Галатии, Каппадокии, Асии и Вифинии, к которым писал своё первое послание. Затем ап. Пётр со своим учеником Марком проповедовал в Вавилоне Египетском, и в Александрии ап. Марк основал церковь. Посетил ап. Пётр и Коринф после того, как ап. Павел основал там церковь.
