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