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