Мы знаем, что еще до проповеди Павла, христианство утвердилось в главных центрах Римской Империи — в Антиохии, в Александрии, в Риме. Но это было всё то же иудео-христианство: его приносили евреи рассеяния, совершавшие традиционное паломничество в Иерусалим для молитвы и жертвы в храме. Таких пришельцев мы уже видели среди слушавших первую проповедь Петра в день Пятидесятницы. Приняв христианство и вернувшись к себе, они основывали общины в еврейских колониях больших городов. Но это не было выходом за пределы иудейства, спор о христианстве оставался внутри-еврейским спором. Так, например, по словам римского историка Светония, в 49 г. император Клавдий выселил всех евреев из Рима из-за беспорядков среди них по вопросу о некоем Христе.
Павел тоже начал свою проповедь в Малой Азии с евреев. В Деяниях не раз повторяется следующая схема: придя в город, Павел входит в местную синагогу, и, основываясь на Писании, читавшемся в ней каждую субботу, начинает проповедь о Христе. Евреи, за немногими исключениями, отвергают его и тогда он обращается к язычникам. Павел никогда не усумнится в том, что евреям «первым надлежало быть проповедану слову Божию» (13, 46). Отвержение ими Христа будет его «непрестанным мучением». «Я желал бы, — сказал он, — сам быть отлученным от Христа за братьев моих, родных мне по плоти» (Рим. 9, 2—3). Но столь же несомненно для него теперь и то, что Евангелие обращено ко всему миру — «во спасение до края земли». Отвергнутый евреями, он до конца осознает свое призвание — быть Апостолом язычников и с ними отныне соединяет свою судьбу.