cts claims that Barnabas was a Cypriot by birth, but his heritage goes unremarked during the account of their visit. Starting in Salamis, they traveled from synagogue to synagogue across the length of the island. Cyprus had a small but well established Jewish community. Ties to mainland Palestine had been preserved since the time the island was a Phoenician territory. Like the Jews, the Phoenicians were a Semitic people. They had a long and noteworthy history as sea-traders who had controlled the Mediterranean until the conquests of Alexander. Cyprus was annexed to Rome in 58 BCE, not for strategic or commercial interests, but because the island's ruler had offered pirates too small a ransom for the release of a captive Roman. Movement between Cyprus and the coastal cities to the East was common, and Paul and Barnabas might have met fellow believers who had fled Jerusalem after the stoning of Stephen. Paphos was the main religious center of Cyprus. Said to be site where the Greek goddess Aphrodite rose to life from the sea, the city attracted visitors to Temple of Aphrodite. Paul and Barnabas sailed from Paphos back to the mainland, disembarking in Perge.

It seems the missionaries did not spend much time in the coastal cites of Attalia and Perge, but passed through them mainly as an artery to the interior. Flooding rivers and rogue bandits presented land travelers -- on foot or with pack animals -- with great dangers. The cities between the coast and the Taurus mountains had adapted to Roman rule, and were stable enough to abandon their fortifying walls. Paul and Barnabas now took to the roads, and likely averaged between fifteen and twenty miles a day. The impressive Roman roads heading inland rose steeply from the coastal plain to cross the mountain range to the upland plain. With peaks up to 11,000 feet, mountain passes were impassable in winter. They were used mainly for the transportation of troops and supplies to Roman military posts, as well as the transportation of commodities like wool and quarried rock from the interior to the ports down below. Although Rome had consolidated the territories into efficient provincial outposts, the region had a long history of nomad populations, local tyrants, foreign rulers, and invading tribes. The rugged mountains and many rivers provided natural boundaries, and isolation allowed preservation of ethnic identities, customs and sometimes languages. Contemporaneous descriptions of the region's ethnic variation included Parthians, Medes, Armenians, Cilicians, and Pisidians to name just a few.

Having passed through the mountains, Paul and Barnabas came to a city called Antioch near Pisidia, a city in Galatia. It was one of sixteen cities named Antioch which a Hellenistic king had founded and named after his father. Galatian was the Greek term for the Celts, and the region was named after the Celtic tribes who had migrated to central Turkey as mercenary soldiers or invaders in the third century BCE. Antioch near Pisida was the most important Roman colony in the interior. Heading East on another military road, Paul and Barnabas next visited Iconium, Lystra and Derbe. A later work called the Acts of Paul and Thecla relates how Paul converted a young woman named Thecla in Iconium. In Lystra, Paul and Barnabas were mistaken for Gentile gods after Paul miraculously healed a lame boy. This story is in the book of Acts, and, like much of Acts, it bears a certain resemblance to other classical literature -- in this case, a myth included in the epic poem Metamorphoses, written by the Roman poet Ovid during the reign of Augustus. The poem collected together hundreds of myths from many regions and combined them into a story to tell the history of the world from its beginning to the present day. In one story, the gods Jupiter and Hermes visit an elderly couple in the region around Lystra. The gods come disguised as mortals, and repay the couple's hospitality by granting one wish. It is a common enough folktale, but, according to Ovid, the local people still venerated the site of the miracle, and brought garlands and visitors to honor the couple. It could be that Ovid himself had visited the site while making a grand tour as a young man.

All four cities of the interior had relatively small Jewish populations, and it may be that it was in these cities that Paul first took his message directly to Gentiles, and initiated congregations separate from synagogues. It is not clear why Paul and Barnabas decided to retrace their steps on the return voyage; the road they were on would have taken them more directly to Tarsus. But retrace they did, and soon sailed back to Antioch in Syria. The congregations Paul had established on this first mission would continue to receive his guidance and support, in letters and visits, for years to come.