在安提阿的教會時期，受到聖靈的指示，掃羅(即保羅)與巴拿巴同去作聖靈召他們所作的工。他們既被差遣後，就下到西埃基，那裡離安提阿約十六里。他們由此坐船往居比路去,居比路即現在的塞浦路斯，是為保羅的第一次宣教旅程(主後46-48 年)。

原來塞浦路斯正是巴拿巴的故鄉，是地中海東部最大的一個島，在今天來說，基督徒居北、回教徒居南。巴拿巴與保羅二人走遍全島，但路加只記他們在撒拉米及帕弗的工作。

撒拉米是今日塞浦路斯東岸的大城 Famagusta 以北約五公里處的一廢墟，但在主前十一世紀，卻是塞浦路斯的主要港口。據說當年在撒拉米廢墟曾有大量猶太人移居於此，猶太會堂林立，並且可以找到巴拿巴的墳墓及以他為名的修道院。

當時保羅到當地傳教的策略是以猶太會堂為據點，因為除了以猶太人為對象外，還可以吸引一批像哥尼流一樣較虔誠的外邦人。當猶太人抗拒福音時，他才將目標轉向外邦人。

不過此一策略也利弊不一,首先因他們被視為不同道的破壞分子，遭過死硬派的猶太保守分子的逼迫，不是拳打腳踢，棒擊石投，便是告諸官府而下獄，屢見不爽，遭受逼迫的例子，層出不窮。其後他們又來到帕弗，遇到一個通曉法術冒充先知名叫巴耶穌的人。