The journey began from Seleucia, the seaport of Antioch (Acts 13:1-4). (Note that there were 2 cities named Antioch - Antioch Of Syria, their starting point, and one in Turkey that they visited). Paul (then still called Saul) and Mark sailed across to Cyprus, some 80 miles (130 kilometers) to the south-west. At this point in time, Barnabas was still the senior member over Paul, who was a relative newcomer after his conversion on the Road To Damascus. That would soon change.

After landing at Salamis, and proclaiming the Word of God in the synagogues (Acts 13:5), they traveled along the entire southern coast of the island of Cyprus until they reached Paphos (Acts 13:6). There, Sergius Paulus, the Roman proconsul, was converted after Paul rebuked the evil sorcerer Elymas (Acts 13:6-12). It was at that point that Paul effectively became the leader. He was from then on called Paul, rather than his former name, Saul.

From Paphos they then sailed north up to the Asian mainland in what is today Turkey. They traveled the short distance up the river Cestrus to Perga in Pamphylia (Acts 13:13), where Mark left them and returned to Jerusalem.html">Jerusalem. It is uncertain why he left, however his young age is usually considered to be a factor. He may simply have become homesick during what became a 2 year mission.

Paul and Barnabas then continued inland for about 100 miles (160 kilometers), up to Pisidian Antioch. Many were converted by Paul when he made his first recorded address there (Acts 13:16-51). Not long afterward however, they encountered persecution from certain people who refused to hear the gospel. After being expelled from the region, "they shook the dust from their feet in protest against them and went to Iconium." (Acts 13:51)

After traveling southeast to Iconium, they again made many converts among Jews and Gentiles (Acts 14:1), but they were again persecuted. This time they would have been killed (Acts 14:5) if they hadn't discovered the plot and fled quickly from the city (Acts 14:6).

From there they continued southward to Lystra where they again made converts (Acts 14:8). Unfortunately, the people of the city, who were accustomed to idolatry, went too far in their esteem for Paul and Barnabas, who they proclaimed as "gods." (Acts 14:11-18). Paul and Barnabas quickly tried to explain that they were merely men sent to teach, but it didn't go over very well with a number of the people. Some of the persecutors from Antioch and Iconium had followed them and incited the crowd. Paul was stoned, dragged out of the city, and left for dead. "But after the disciples had gathered around him, he got up and went back into the city. The next day he and Barnabas left for Derbe." (Acts 14:20).

After preaching the good news in Derbe, they then returned back along their entire route, through Lystra, Iconium and Antioch, "appointing elders for them in each church" (Acts 14:23). They then continued southward through the regions of Pisidia and Pamphylia until they arrived at the seaport of Attalia (Acts 14:24-25). From there, they boarded a ship and sailed back home to Antioch, where they had began 2 years before. "On arriving there, they gathered the church together and reported all that God had done through them and how He had opened the door of faith to the Gentiles." (Acts 14:27).

See also Paul's Second Missionary Journey and Paul's Third Missionary Journey.