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