Саул, видимо, осознавал эти трудности. Мессианство было для него делом всеобщим, а не только евреев. Вера в Иисуса не требовала (на его взгляд) принятия политических и национальных устремлений иудаизма. Обрезание он считал устаревшим ритуалом и твердо верил, что «…тот Иудей, кто внутренне таков, и то обрезание, которое в сердце, по духу, а не по букве…» (Римлянам, 2:29).
Поэтому Саул принял романское имя Павел и начал открыто проповедовать язычникам, прося их признать Иисуса без всякого обрезания и следования всем деталям обряда, принятым у фарисеев. Везде, где он побывал, появлялись христианские общины, разраставшиеся за счет язычников.
Несоблюдение обряда обрезания среди новообращенных язычников привело евреев в ужас, и в результате между ними и христианами разрасталась пропасть. На самом деле это покоробило даже тех евреев, которые признавали Иисуса, так что на какое-то время христианство разделилось на две группы: обрезанные еврейские христиане, полностью признававшие Закон Моисея и одно временно верившие в мессианскую роль Иисуса, и необрезанные христиане-неевреи, которые были склонны интерпретировать учение Иисуса в свете греческой философии.
Две эти позиции столкнулись лоб в лоб в 48 г. на совете Иерусалима. Яков, брат Иисуса, отстаивал еврейско-христианские взгляды, а Павел — точку зрения христиан-неевреев. В результате Павел одержал победу, и пути христианства и национального иудаизма разошлись.
Примерно в 57 г. Павел возвратился из своего третьего миссионерского путешествия и посетил Иерусалим. Там его опознали евреи, смотревшие на него как на человека, пропагандировавшего учение, которое противоречит Закону Моисея, и поэтому считавшие, что его присутствие оскверняет храм. Хуже того, распространился слух, что он привел в храм язычников. Начался бунт, и линчевание казалось неизбежным, если бы Павла не защитили римские солдаты.
У римлян по-прежнему были неприятности с этой беспокойной провинцией. После смерти Ирода Агриппы ею управляли без особого успеха несколько прокураторов, и с 52 г. прокуратором стал Антоний Феликс. Он женился на Друзилле, дочери Ирода Агриппы I, но это не спасло положение, и ситуация продолжала ухудшаться.
Павла привели к Феликсу, обвинив его в осквернении храма, и он защищался как фарисей, поддерживавший идею о воскрешении Иисуса, указывая, что воскрешение является важным догматом фарисейской веры. Но когда Павел заговорил о неизбежном конце света, Феликс отмахнулся от него как от сумасшедшего. Скорее для того, чтобы всех успокоить, чем по каким-либо иным соображениям, он приказал посадить Павла в тюрьму.