Нельзя при этом не заметить, что в ряду противников христианской религии почти всегда первыми и упорнейшими были иудеи — замечание, подтвержаемое не только историей апостольского служения Павлова, но и всей историей христианства первых веков. Закоренелый предрассудок, гласящий, что они одни вследствие завета Божия с Авраамом имеют право на благодеяния Божии, ниспосланные в лице Мессии, ложное мнение, сводящееся к тому, что исполнения обрядового закона достаточно для оправдания себя пред судом Божиим, и другие заблуждения, питаемые гордостью и корыстолюбием, преграждали путь к сердцам иудеев благотворному учению о вере во Иисуса Христа. Им нужна была не такая религия, которая уравнивала бы их с язычниками, ими презираемыми, а такая, которая еще более возвышала бы их мнимые права и преимущества.
Не таково было состояние язычников. Им нечем было хвалиться во плоти, они не считали своими предками Авраамов и Давидов,
На обратном пути в Антиохию Павел снова посетил своих учеников в Листре, Иконии и Антиохии Писидийской. В его отсутствие они должны были претерпеть много зла как от иудеев, так и от язычников, оставшихся во тьме идолопоклонства, а потому присутствие его было для них присутствием Ангела-утешителя. Земные утешения не могли иметь места в этом случае: вера питается не землею, а небом. Павел старался открыть для них неисчерпаемый источник утешения в самом существе принятой ими религии, вразумляя их, что Царствие Божие, внутреннее соединение с Богом в духе, не иначе может быть достигаемо, как путем скорбей и искушений. Для устроения внешнего порядка между новообращенными, распространения истинной веры и благодеяния он рукоположил к каждой Церкви пресвитеров и, препоручив их Господу, отправился со спутниками в дальнейший путь. Пройдя через Пергию, в которой они проповедовали слово Божие, путешественники достигли Атталии, из которой отплыли обратно в Антиохию. По их прибытии немедленно собрались верующие: каждый желал услышать об успехах проповеди. Повествование Павла исполнило сердца всех радостью и благодарением Промыслу, который отверз дверь веры для язычников.
В апостольских Деяниях не сказано, как долго продолжалось первое путешествие Павлово по обращению язычников. Надобно полагать, что оно длилось около двух лет. Нужно было время и на путешествие, и на проповедь, и на устроение новосозидаемых Церквей. Так, о пребывании Павла в Иконии сказано, что оно продолжалось довольно долго (см.: Деян. 14, 3), притом что Апостолы проповедовали еще и в некоторых других городах, о которых не упоминает святой Лука (см.: Деян. 14, 6).
Пробыв довольно долго в Антиохии, Павел должен был в третий раз идти в Иерусалим. Поводом к этому путешествию было нестроение, происшедшее в Антиохийской Церкви, виновниками которого были иудействующие христиане. Придя из Иерусалима, они, возроптав, начали внушать братиям, что без соблюдения обрядового закона, особенно без обрезания, невозможно получить спасение. Павел с Варнавою ревностно восстали против этого заблуждения, столь несовместимого с христианскою свободой. Уважение, которым они пользовались за свои апостольские труды, придавало значимость их мнению, но при необходимости выходцы из Палестины могли сослаться также в качестве примера и на старейших Апостолов, обычаи Иерусалимской Церкви и тому подобное. Споры, происшедшие по этому случаю, окончились ничем, и юная годами Церковь Антиохийская, не имея возможности самостоятельно разрешить возникшие недоумения, решилась прибегнуть к совету своей Матери — Церкви Иерусалимской, положив Павлу и Варнаве отправиться по этому делу к Апостолам и пресвитерам в Иерусалим. Для отвращения подозрений в пристрастии, они взяли с собою некоторых из братий, вероятно, таких, которые придерживались противного мнения.