After their important conciliatory visit to Jerusalem, Acts tells us that Paul and Barnabas began their travelling mission around the Mediterranean world. To be more exact, they returned to Antioch, and it was when the church there was worshipping and fasting that God said through the Holy Spirit, 'Set apart for me Barnabas and Saul for the work to which I have called them' (Acts 13.2).
There are two interesting things to be noticed here. First, this sending out, like the previous sending of them to Jerusalem with famine relief, was is in response to a prophecy. We are dealing with a church where prophecy under the inspiration of the Holy Spirit seems to have been very important. But second, if we are right about the Galatians 2 background, this prophecy did not come out of the blue; as we have seen, it may be said to have picked up on the commission that Paul and Barnabas had been given in Jerusalem to 'go to the Gentiles'. Just as the earlier prophecy of Agabus may have confirmed something that they felt was important – that a delegation should go to Jerusalem – so here it is as though the Holy Spirit, who had sorted things out in Jerusalem, was now guiding them to implement what had been agreed.
So from Antioch, capital city of the east of the Roman Empire, the city where the first strong Gentile church was established, the missionaries ('apostles' means missionaries) to the Gentiles went out, with the blessing and support of the church.
They went first to the island of Cyprus, prompted no doubt by the Holy Spirit, but it was also a very logical place for them to go, since Barnabas was a Cypriot and the Antioch church had other links with Cyprus (Acts 4.36, 11.20). Acts describes the two missionaries travelling through the whole island, and making at least one convert, who is no less than one Sergius Paulus, the proconsul (prime minister, we might say) of the island (13.12).
From Cyprus they sailed north across the Mediterranean Sea to