Так как Варнава был родом с Кипра, участникам миссионерского путешествия показалось наиболее естественным начать свои труды с этого острова, где для одного из членов команды все было знакомо. Кипр уже около столетия был римской колонией, сначала как часть Киликии, а затем как самостоятельная провинция. Апостолы высадились в Саламине, греческом поселении на восточном побережье острова (сейчас там на предполагаемом месте их высадки стоит стела с отрывком из 13-й главы Деяний апостолов). Они прошли весь Кипр и пришли в Пафос, город, который существует и поныне.

С давних пор на Кипре жило много евреев, и поэтому собравшиеся в субботу в синагогу стали первыми слушателями посланцев Антиохийской церкви. Ведь синагогальное богослужение, в отличие от храмового, вели миряне, и любой уважаемый человек мог читать Писание, а затем толковать его и произносить проповедь на тему прочитанного отрывка. Старейшины синагоги предложили сделать это Савлу и Варнаве. Мы сразу же встречаем на Кипре не только людей, противящихся апостолам, но и тех, на кого их слова оказали сильное воздействие. Евангелист Лука даже сообщает, что среди поверивших оказался проконсул Кипра Сергий Павел, человек из богатой и знатной семьи. В рассказе о посещении Кипра апостол в последний раз назван Савлом (Деян 13.9), отныне будет употребляться только его римское имя Павел.

С Кипра группа миссионеров вернулась в Малую Азию, приплыв, вероятно, в Атталию (современную Анталию). Они обошли несколько городов южного побережья: Пергу, Антиохию Писидийскую, Иконий, Листру и Дербу. Эти города в то время входили в состав римской провинции Галатия, хотя и были населены не галатами (это одно из кельтских племен, переселившихся из Европы в Малую Азию, родственное галлам), но людьми других национальностей (фригийцами, писидийцами, ликаонцами и др.) Перга – главный город Памфилии, территории между Таврийским хребтом и Средиземным морем. Там проживало в то время большое количество евреев. Несомненно, Павел со спутниками побывал у них в синагоге с проповедью о приходе Помазанника.

Здесь же, в Перге, произошло в высшей степени неприятное событие: Иоанн Марк отказался сопровождать их дальше и вернулся на родину. Причины этого поступка неизвестны, но, вероятно, Иоанну Марку претила мысль проповедовать язычникам, не требуя от них соблюдения Закона Моисея с его обязательным обрезанием. Известно, что перед началом второго миссионерского путешествия Варнава снова хотел взять с собой Марка, но Павел так решительно запротестовал, что это рассорило ближайших друзей, и они надолго расстались. Вряд ли это можно объяснить причинами личного характера, ведь апостол, как видно из его писем, всегда умел встать выше личных обид. В его Письме галатам есть туманные слова о неких лжебратьях, которые вкрались в окружение апостола с неблаговидной целью воспрепятствовать христианской свободе и вернуть последовавших за Христом обратно в рабство Закона. Некоторые ученые видят в этом намек на Марка, хотя это не более чем гипотеза. Но если это действительно так, то приятно сознавать, что позже Павел и Марк примирятся и снова станут единомышленниками и сотрудниками, полностью доверявшими друг другу. Марк не покинет апостола даже в тюрьме. 

Из Перги Павел вместе со своими друзьями отправился в высокогорную Антиохию Писидийскую. По мнению некоторых ученых, в болотистой и жаркой Памфилии Павел заболел малярией и ушел во Фригию (эта Антиохия относилась к области Фригии), где климат был здоровее. Евангелист Лука рассказывает о том, какую проповедь произнес Павел в тамошней синагоге. Интересно отметить, что она во многом совпадает с тем, что говорил Петр во время Пятидесятницы. Затем они отправились в Иконий. Вероятно, память о пребывании Павла в этом городе сохранилась так крепко, что позже, в апокрифе «Деяния Павла и Теклы» главные события произойдут именно здесь.

Во всех этих городах Павел и Варнава начинали свою проповедь с синагог, а в том случае, если не встречали там понимания и веры, обращались к язычникам. И мы видим, что одни слушатели отвечали на их слова верой, другие же – насмешкой и ненавистью. Так, из Антиохии Писидийской их выгнали, потому что неверующие евреи сумели восстановить против них благочестивых женщин из знати, которые, вероятно, принадлежали к числу боящихся Бога (так назывались люди, поверившие в единого Бога Израиля, но по каким-то причинам еще не полностью соблюдавшие Закон Моисея), а те, в свою очередь, настроили против апостолов первых людей города, вероятно, своих мужей и родственников. Апостолы и дальше будут встречать постоянную оппозицию чаще всего со стороны своих единоплеменников. Но все же после их ухода в Писидии осталась христианская община, и ее члены были исполнены радости, несмотря на то что вражда окружающих распространялась и на них.

Апостолам пришлось бежать и из Икония (в 150 км от Антиохии; это современный турецкий город Конья), где против них составился заговор и где им даже угрожала смерть. Они отправились в Ликаонию, в город Листру (в 18 км от Икония). В Листре их проповедь имела большой успех, тем более что Павел совершил там чудо, вернув здоровье человеку, у которого от рождения были парализованы ноги. Правда, реакция горожан была такой, что доставила апостолам не столько радость, сколько огорчение. Толпа собравшихся послушать их и своими глазами увидевшая чудо, решила, что к ним сошли олимпийские боги в человеческом облике. Варнаву они сочли Зевсом. Он, вероятно, был человеком величавым и осанистым и больше походил на главу олимпийцев, чем невзрачный Павел. А так как говорил по большей части Павел, то его приняли за вестника богов Гермеса. Горожане жаждали совершить в честь посетивших их «богов» жертвоприношение, и апостолам лишь с большим трудом удалось их отговорить.

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

Из Атталии, где апостолы уже побывали, приплыв туда с Кипра, они отправились на корабле в Антиохию Сирийскую. Христианская община Антиохии послала их в миссионерское путешествие, и поэтому апостолы возвратились туда, чтобы дать ей отчет о результатах своей деятельности. К сожалению, неизвестно, сколько времени длилось первое миссионерское путешествие. Многие предполагают, что оно заняло около трех лет, примерно с 46 по 49 год.