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