|Paul was certainly a Jew and, by his own testimony, a Pharisee, but he was not a Judean. According to Acts 21:39, he announced when a captive in Jerusalem that "I am a Jew, from Tarsus in Cilicia, a citizen of no mean city...." Now Cilicia, a province of Rome, was in Anatolia, not in Judea, and Tarsus a city on it's Mediterranean coast (see the Turkey map, then use your back button to return here). It is easy to see, then, that Paul most likely was familiar from a very early age with the region in which he was to travel.|
By Paul's time (40-60 CE) Roman roads crisscrossed Anatolia, making travel feasible not only along the coast or by sea but through the heartland. Where precisely did Paul go? His letters and the Acts account show that he established churches in at least two of the Roman provinces in Anatolia: Galatia and Asia. There is ample evidence, for instance, that he lived and worked in Ephesus in Asia. But his letter "to the churches of Galatia" specifies no particular city, nor does it detail in what part of the province the churches are located.
Chief among those factors is Paul's exclamation, "You foolish Galatians!" (Gal. 3:1). This direct address to members of his congregation becomes revelatory when the Greek word, Galatai,is understood literally to mean "Celts." Like Luke, Paul uses an ethnic designation, not the Roman political one. But Celts?
Yes, Celts. In the third century BCE Celtic tribes moved into Thrace (Greece), where they were repulsed, after which they came across the Bosporus into the area south of the Black Sea and settled there, probably with the concurance of rulers such as Mithridates VI of Pontus. It would be natural for Paul to address people living there as Celts; he would have been very unlikely to so name people living in, e.g., Lystra. The "churches of Galatia" most likely were located in the major cities of the ancient Celtic settlement: Ankyra, Pessinus, and Tavium (see Turkey map).
Tourist guides and guide books may declare that Paul came through Cappadocia; probably he did not. If he passed through Byzantium (Constantinople; Istanbul) he left no footprint. Both places would appear to be "naturals" as we look at the map. Rabbinic sources indicate that Cappadocia was a major Jewish center in the first centuries BCE and CE but there is scant evidence of Jewish presence in Byzantium, which was a "free city" in Bithynia province at the time. Paul apparently tarried in Galatia orginally because he got sick in one of those cities when he was on his way to somewhere else (Gal. 4:13). To where? It's anyone's guess, but at Acts16:7, in a passage that scholars find problematic, Luke guesses that "they tried to go on into Bithynia, but again Jesus' spirit would not allow them." Whatever that might mean, it is virtually certain that Paul never made it to Byzantium or, if he did, he didn't tell us about it.