Они отправились в путь, как видно, сопровождаемые Иоанном-Марком, который должен был услуживать им и помогать, крещая новообращенных и исполняя второстепенные обязанности. Прежде всего они отправились на остров Кипр, ближайший к Антиохии остров Средиземного моря. Это место было самым подходящим для того, чтобы с него завязать сношения со всем остальным языческим миром. Варнава был сам родом с этого острова, на нем жило много иудеев; по самому островному положению они должны были ближе общаться с языческим населением, чем на материке; как занимавшиеся морскою торговлею, жители острова имели обширные связи с окружающими материками, особенно с южными областями Малой Азии, куда и отплыли потом апостолы. Чтобы отправиться из Антиохии в Кипр, они должны были прийти в Селевкию — небольшой портовый городок при впадении реки Оронта, на которой лежала Антиохия. Здесь они сели на корабль и отправились в Кипр, высадившись затем на восточном берегу острова в городе Саламине. Так как Варнава был родом из кипрских иудеев, то естественно, что они обратились с проповедью о Христе прежде всего к тамошним иудеям по их синагогам. Св, Павел и позже держался правила проповедовать сначала иудеям, а потом уж язычникам. Для исполнения разных поручений они имели при себе Иоанна-Марка. Из Саламина они пошли далее на запад и прошли весь остров до города Пафа, лежавшего на западном побережье. Это был главный город — местопребывание римского проконсула, правителя Кипра. Там они нашли некоего волхва, в том же смысле, в каком этим именем назывался самарянский Симон Волхв, по имени Вариисус (что, собственно, значит «сын Иисуса»). Дееписатель клеймит его именем лжепророка. Сам же он был иудеянин, хотя и носил почему-то арабское имя Елима, быть может потому, что был родом из Аравии, или просто присвоил себе это имя, дабы слыть за восточного мудреца.

Видимо, этот волхв имел влияние на проконсула Сергия Павла, которого Дееписатель называет «мужем разумным», так как пытался отвратить его от веры во Христа. Можно полагать, что проконсул этот не удовлетворялся языческой религией и держал при себе иудейского волхва, надеясь в его мудрости и учении найти себе удовлетворение, но не найдя этого, пожелал обратиться к проповедникам нового учения, пришедшим в его город. Елима, что в переводе и значит «волхв», воспротивился им, боясь потерять свое влияние на проконсула. «Но Савл, он же и Павел, исполнившись Духа Святого и устремив на него взор, сказал: о, исполненный всякого коварства и всякого злодейства, сын диавола, враг всякой правды…» — и поразил его слепотой. Это обличение волхва, соединенное с чудесным знамением, произвело такое впечатление на проконсула, что он, уже без колебаний, уверовал во Христа. Здесь замечательно то, что отныне Савл перестает называться этим именем, а именуется далее уже Павлом — имя, с которым он и вошел в историю. Большинство древних толкователей полагают, что эта перемена имени произошла вследствие того, что Савл, после первого совершенного им великого чуда и обращения проконсула Сергия Павла, ставшего его первым духовным чадом в его апостольской деятельности, принял на себя, в память этого знаменательного события, имя проконсула — Павел. Характерно, что с этого времени Павел, как явивший в себе особую силу Духа Божия и тем показавший себя главным апостолом языков, ставится на первое место. В то время как до этого события Дееписатель имя Варнавы ставил первым и писал «Варнава и Савл», с сего времени он постоянно пишет: «Павел и Варнава». Другие толкователи высказывают предположение, что Савл — это еврейское имя, а Павел — это римское имя, которое носил Савл от самого своего рождения как римский гражданин, что было в употреблении у иудеев. В начале, как истовый фарисей, он именуется своим еврейским именем Савл, когда же он вышел на проповедь языческому миру, он стал употреблять свое римское имя.