В юности Павел приехал в Иерусалим для того, чтобы изучать Тору. Возможно, это произошло уже после казни Христа. По крайней мере, учеником Иисуса он не был, чудес Его не видел и оставался после Его казни правоверным иудеем. Когда в 37 г. в Иерусалиме начались гонения на христиан, Савл принял в них самое живое участие. Именно он охранял одежду тех, кто побивал камнями первомученика Стефана. Сам Савл, правда, не кидал в него камней, но всецело одобрял это убийство. И позже он деятельно помогал гонителям. В книге Деяний святых апостолов говорится, что Савл «терзал церковь, входя в дома и влача мужчин и женщин, отдавал их в темницу». Затем, «еще дыша угрозами и убийством на учеников Господа», он пришел к первосвященнику и выпросил у него письма в Дамаск, чтобы искать там по синагогам последователей Христа и приводить их на мучения в Иерусалим.
И вот, когда он шел по дороге и уже приближался к Дамаску, его внезапно осиял небесный свет. Юноша упал на землю и услышал голос, говорящий ему: «Савл, Савл! Что ты гонишь Меня?» Он спросил: «Кто Ты, Господи?» Господь отвечал: «Я Иисус, Которого ты гонишь. Трудно тебе идти против рожна». Савл в трепете и ужасе сказал: «Господи! Что повелишь мне?» И Господь повелел: «Встань и иди в город; и сказано будет тебе, что тебе надобно делать». Голос утих, но Савл был так потрясен, что по приходу в Дамаск три дня ничего не видел, не ел и не пил, а потом принял крещение от одного из христианских проповедников по имени Анания и стал сам проповедовать по синагогам об Иисусе и о том, что Он есть Сын Божий. Все слышавшие это дивились и спрашивали: «Не тот ли это самый, который гнал наших единоверцев в Иерусалиме?»
В Дамаске Павел прожил три года (с 38 по 41-й), но вынужден был покинуть его после того, как местные иудеи решили его убить. Он тайком отправился в Иерусалим и здесь попытался пристать к апостольской общине. Поначалу к нему относились с подозрением и не верили в искренность его обращения, пока из Дамаска не прибыл Варнава, пользовавшийся у апостолов большим авторитетом, и не подтвердил, что это чистая правда. Павел стал проповедовать в Иерусалиме. Когда это сделалось опасно, он перебрался в Антиохию-на-Оронте. Этот огромный город с полумиллионным населением в то время считался подлинной столицей Востока. Большинство жителей здесь были греки, а среди других народностей наряду с сирийцами преобладали евреи. Около года Павел проповедовал здесь вместе с Варнавой и обратил к Христу немалое число людей, как иудеев, так и язычников. Последние даже значительно преобладали над первыми. Именно в Антиохии верующие в Христа впервые получили прозвание
Одним из первых таких миссионеров стал Павел. В 42 г. он вместе с Варнавой отправился проповедовать на Кипр и прошел весь остров от Саламина до Пафа. Тут его захотел послушать римский проконсул Сергий, но один из иудеев – Елим Волхв – противился этому, стараясь отвратить проконсула от нового вероучения. Тогда Павел, устремив на него взгляд, сказал: «О, исполненный всякого коварства и всякого злодейства, сын дьявола, враг всякой правды! Перестанешь ли ты совращать с прямых путей Господних? И ныне вот, рука Господа на тебя: ты будешь слеп и не увидишь солнца до времени». И в тот же миг Елим лишился зрения. Проконсул, ставший свидетелем этого чуда, уверовал в Христа.