Acts 4:38; 11:19,20; 13:4; 15:39; 21:3,16; 27:4

Departing from the Seleucian port, some 16 miles from Antioch, the team arrived by ship into the port of Salamis on the eastern side of Cyprus in an undisclosed amount of time (probably two days by sail depending on winds). After preaching in the synagogues of the city, they proceeded across the island as far as Paphos, a port on the west of the island (Acts 13:4-6).

The long island of Cyprus (225 kilometers) is the largest island of the eastern Mediterranean, situated about 100 kilometers off the Syrian coast (as well as the same distance south of the Turkish coast). Cyprus is not mentioned by name in the Hebrew Scriptures, but reference to the "Kittim" (Gen. 10) was probably the inhabitants of Kition (near modern Larnaca). By the time of St. Paul's journeys, Rome was mater of the island, though it acted with much autonomy.

Though Cyprus was log considered an ally of Rome, it was historically Egyptian controlled. The island became a Roman province in 58 BCE (initially as an annex of Cilicia), but in 47 BCE the island was returned to Egypt. With the suicide of Cleopatra (31 BCE), Cyprus came under direct Roman control. Later (22 BCE) Augustus proclaimed Cyprus one of the senatorial provinces under a praetorian Proconsul.

The specific route of their land journey is not specified in the text, yet there are arguments to suggest the route may be along the major Roman route of the day. First, St. Paul and St. Barnabas appear to intend to make their way in haste, and do not plan to spend an excessive amount of time in any one city. Though they had been directed by the Spirit of God and the Church at Antioch, the actual plan of the trip is undisclosed in the narrative. Second, on other journeys they took advantage of the Roman roads. Scholars suggest that St. Paul used the Via Sebaste to access Pisidian Antioch in the First Journey, as well as the Via Egnatia to cross from Neapolis to Berea in Macedonia in the Second Journey.

In the case of the Cyprus journey, the men had opportunity to access a roadway from the east coast of Cyprus to the west. They apparently had two choices for the journey, one following the northern coast, and one to the south. A number of scholars have accumulated careful evidence for the roads between Salamis and Paphos using traveler itineraries found in Roman record, and following the archaeological discoveries of Roman milestones.

The route favored by scholars was that which headed for Citium on the south coast, westward to Amathus, continuing to Curium and terminating in Paphos. The southern journey could have been made between Sabbaths, but may have extended a day or two longer. The route no doubt took them along the path of some significant pagan centers.

Though the only cities on Cyprus mentioned in the narrative of Acts are Salamis and Paphos, St. Paul and St. Barnabas no doubt traveled by way of other cities en route. If they used the road along the south coast as suggested, they would have passed through Citium, Amathus and Curium before reaching Paphos. Amathus had been granted the status of asylum in 22 CE because of their civic sanctuaries, as had the cities of Salamis (Olympian Zeus) and Paphos (Paphian Aphrodite). Amathus boasted a sanctuary of Aphrodite.

St. Barnabas and John Mark returned to the island when St. Paul left with Silas to Asia Minor to take the message of the Jerusalem Council (Acts 15:39) but no firm knowledge of their itinerary was preserved. The mark of St. Barnabas on the island is unmistakable in the various traditions and local churches.