fter establishing their Antioch base, Paul and Barnabas reached out to other cities in the conviction that greater numbers of believers would hasten the Messiah's return. The account of these missions in the Book of Acts includes stories of miracles, successes and failures. In several cases, Acts finds the missionaries being chased out of town by angry crowds, or subject to attempted stonings. Their first mission took them to Cyprus, along the coast of Modern Turkey, and then inland as far as Galatia. Although travel was difficult, and he sometimes met hostility, Paul would devote the rest of his life to missionary work, establishing and guiding congregations according to his vision. He would log thousands of miles over land and sea, and face opposition from friends and foes alike. On this first mission, Paul and Barnabas concentrated on delivering their message to the synagogues, although they also welcomed gentiles to join their cause.

Leaving Antioch, Paul and Barnabas would have traveled down the Orontes and boarded a ship in Seleucia Pieria, the port city at the river's mouth on the Mediterranean. It is likely that they would have found passage on a cargo ship. Passenger ships were few, and it was common for cargo ships to take on passengers as their loads allowed. Travel was surprisingly common in the Roman period. Although subject to storms and seasons, travel by sea was often safer, faster, more comfortable and less expensive than travel by land. Piracy had been suppressed in the Mediterranean for over a century by the time Paul took his mission to sea, but banditry along the roads continued. Ships were crowded with cargo such as wine and oil in large clay jugs called amphorae, grain, spices and nuts, and bolts of cloth. Ships usually hugged the coast and made frequent stops at port cities along the way. The first stop for Paul and Barnabas was Cyprus.