Перед отправлением в путешествие он, невзирая на различие мнений, выразил сыновние чувства к Иерусалимской Церкви — Матери всех церквей. Для этой цели он собрал денежные пожертвования в пользу крайне бедствовавших иерусалимских христиан и сам взялся отвезти их в Святой город.
В 58 году вместе с апостолом Лукой он взошел на корабль и отправился в путь. По дороге им приходилось заходить в различные гавани, где их встречали единоверцы. Апостол Павел был горячо любим повсюду, и встречи были самыми сердечными. Братья настойчиво отговаривали апостола от поездки в Иудею, где в это время бурлили страсти и можно было ожидать со дня на день восстания против римлян или гражданской войны. Кроме того, апостола Петра там уже давно не было, и в общине получили преобладание сторонники соблюдения правил Закона, которые были настроены враждебно по отношению к апостолу язычников. Павел сам понимал, что идет навстречу опасности, но оставался непреклонен. «Я готов умереть за имя Господа Иисуса», — говорил он плачущим друзьям… Прощание на берегу, снова море, снова встречи и предостережения. Наконец, корабль прибыл в Кесарию и, после нескольких дней пешего перехода, апостол свободы вступил в город, бывший оплотом ветхозаветного ритуализма.
Апостол Иаков принял собрата радушно, но этого нельзя было сказать о прочих. Павлу посоветовали, чтобы не смущать верующих из фарисеев, исполнить традиционный обряд. Павел согласился, но и это не примирило с ним приверженцев Закона: через несколько дней они натравили на него толпу, обвиняя его якобы в осквернении храма. Римская стража спасла апостола от рук черни и предала его на суд синедриона. На суде апостол расположил к себе часть судей, и дело его в конце концов было передано римскому прокуратору. Этот чиновник, убедившись, что, с точки зрения закона, Павел совершенно невиновен, тем не менее не хотел сразу отпустить его, рассчитывая получить взятку. Так прошло три года. Прокуратора сменили. Назначенный на его место правитель привлек к разбирательству дела Павла царя Агрип-пу II. В результате апостол получил полное оправдание. Но он захотел использовать свое право римского гражданина и апеллировать в императорский суд.
Его требование было выполнено: осенью 60 года корабль с апостолами Павлом и Лукой, а также с арестантами, сопровождаемыми отрядом солдат, покинул сирийский берег. Центурион относился к апостолам сочувственно, разрешал им сходить с корабля для встречи с собратьями.
Путешествие кончилось бедственно: страшный ураган несколько недель носил корабль по волнам, и все, кроме Павла, совершенно потеряли присутствие духа. Наконец, когда судно потерпело крушение у берегов о. Мальты, путешественникам удалось вплавь добраться до берега. В течение всего этого времени апостол Павел держался с невозмутимым спокойствием и проявлял находчивость и смелость в самых трудных обстоятельствах. Явления Господа укрепляли его уверенность в благополучном исходе пути.