w podróży towarzyszył im Jan Marek. Stamtąd skierowali się do Salaminy na Cyprze, przeszli pieszo przez wyspę do Pafos, skąd wypłynęli do Perge w Pamfilii. Wówczas Jan Marek postanowił wrócić do Jerozolimy. Następnie Barnaba i Paweł udali się do Antiochii Pizydyjskiej, a później do Derbe, Ikonium i Listry w Likaonii. Według relacji Łukasza Ewangelisty, Paweł nie prowadził żadnej ewangelizacji na Cyprze, prócz jednego sporu z Elimasem Bar Jezusem, wróżbitą prokonsula Sergiusza Pawła w Pafos. W Listrze natomiast Barnaba i Paweł mieli uzdrowić paralityka, a następnie odrzucić przypisany im hołd jako wcielenia Zeusa i Hermesa. Później Paweł przeżył karę ukamienowania.
Część badaczy podaje w wątpliwość historyczną wiarygodność pierwszej podróży misyjnej, podając argument, że według Listu do Galatów, sam Paweł twierdził, że pozostawał w Cylicji i Syrii przed zebraniem apostołów. Jednak przekazy o podróży na Cypr potwierdzają świadectwa Jana Marka, a pobyt w Antiochii Pizydyjskiej, Ikonium i Listrze – 2. List do Tymoteusza.