У Павла были сложные отношения с руководителями Иерусалимской общины. Он пришел к ним спустя три года после собственной проповеди, виделся там с Иаковом и Петром, с которыми вел переговоры (Галат. 1: 18–19). Многие иудео-христиане не доверяли ему: по свидетельству Деяний апостолов, даже боялись его. Только Варнава, его будущий спутник признал истинность его обращения в христианство и рассказал об этом апостолам (Деян. 9: 26–27). Павел несколько раз бывал в Иерусалиме; он договорился с руководителями Иерусалимской общины, что он и Варнава пойдут к язычникам („народам“ — в греческом тексте), а те — к обрезанным, т. е. иудеям. По существу, Павел, не порывая с иудаизмом (как он пишет в Первом послании к коринфянам — „…для Иудеев я был как Иудей…“ (I Кор. 9: 20), делом своей жизни стал считать обращение в христианство язычников (Галат. 2: 7); по существу, его идеей было, что Царство Божие наступит, когда во Христа уверуют и иудеи, и язычники.
Но не все проповеди приводили к успеху и среди неиудеев. Интересный эпизод, описанный в Деяниях апостолов, произошел с Павлом и Варнавой в Ликаонии (население ее в основном говорило на местном языке), области Малой Азии, мало затронутой греческой культурой. Павел и Варнава подошли к воротам небольшого города Лисгра и начали говорить о Спасителе. Местные жители, по-видимому, плохо поняли их, но темперамент странных гостей, повторяемое ими слово „Бог“ произвели на слушателей впечатление: они решили, что к ним явились сами боги.
Варнаву они приняли за Зевса, а Павла за Гермеса — последнее автор Деяний объясняет тем, что Павел „начальствовал в слове“, но, возможно, внешний вид Варнавы был более внушителен. Жрец святилища Зевса даже хотел совершить им жертвоприношения, привел волов и принес венки. Павел и Варнава всячески пытались разубедить слушателей, даже разорвали на себе одежду, чтобы показать, что они — обычные люди, и с трудом убедили толпу разойтись по домам (Деян. 14: 11–18). Интересно, что археологи раскопали у ворот Листры святилище, посвященное Зевсу, — место действия описано в Деяниях апостолов достаточно верно. Не менее сложно было проповедовать христианство и в крупных городах. В этом отношении важно описание происшествия в крупнейшем городе Малой Азии Эфесе. Во время пребывания там Павла и его спутников против них выступили ремесленники города — серебряных дел мастера (Деян. 19: 25–40). Они изготовляли в качестве сувениров для приезжих серебряные модели храма Артемиды Эфесской, считавшегося одним из семи чудес Света. И вот кто-то из ремесленников подбил товарищей выступить против христиан, которые якобы утверждали, что „делаемое руками человеческими не суть боги“. Толпа ремесленников, схватив спутников Павла, собралась в театре (к ним присоединились и просто любопытствующие) и начала выкрикивать обвинения против христиан и хвалу Артемиде. Стихийное выступление толпы напугало власти. Перед собравшимися выступил грамматевс (должностное лицо, один из сотрудников городского совета; в синодальном переводе — блюститель порядка) и стал успокаивать кричащих, говоря им, что если у них есть жалобы, пусть обратятся в суд или к наместнику, иначе они могут быть обвинены в возмущении, „ибо нет никакой причины, которою мы могли бы оправдать такое сборище“. Этот рассказ отражает реальность общественной жизни в провинциальных городах империи, страх местных руководителей перед римскими властями, стремление избежать несанкционированных сборищ толпы, нежелание ввязываться в религиозные конфликты, а также зафиксированное надписями существование влиятельной гильдии мастеров-серебряников в Эфесе. Понятно, что люди, подобные этим ремесленникам, не примыкали — во всяком случае, на первых порах — к христианам.