The Neolithic populations, which colonized Europe approximately 9,000 y ago, presumably migrated from Near East to Anatolia and from there to Central Europe through Thrace and the Balkans. An alternative route would have been island hopping across the Southern European coast. To test this hypothesis, we analyzed genome-wide DNA polymorphisms on populations bordering the Mediterranean coast and from Anatolia and mainland Europe. We observe a striking structure correlating genes with geography around the Mediterranean Sea with characteristic east to west clines of gene flow. Using population network analysis, we also find that the gene flow from Anatolia to Europe was through Dodecanese, Crete, and the Southern European coast, compatible with the hypothesis that a maritime coastal route was mainly used for the migration of Neolithic farmers to Europe.