Stickleback fishes in the family Gasterosteidae have become model organisms in ecology and evolutionary biology. However, even in the case of the most widely studied species in this family – the three-spined stickleback (Gasterosteus aculeatus) – the worldwide phylogenetic relationships and colonization history of the different populations and lineages remain poorly resolved. Using a large collection of samples covering most parts of the species distribution range, we subjected thousands of single nucleotide polymorphisms to coalescent analyses in order to reconstruct a robust worldwide phylogeny of extant G. aculeatus populations, as well their ancestral geographic distributions using Statistical-Dispersal Vicariance and Bayesian Binary MCMC analyses. The results suggest that contemporary populations originated from the Pacific Ocean in the late Pleistocene, and the Atlantic was colonized through the Arctic Ocean by a lineage that diverged from Pacific sticklebacks ca 44.6 Kya. This lineage contains two branches: one that is distributed in the Mediterranean area, from the Iberian Peninsula to the Black Sea (‘Southern European lineage’), and another that is comprised of populations from northern Europe and the east coast of North America (‘Trans-Atlantic lineage’). Hence, the results suggest that the North American East Coast was colonized by trans-Atlantic migration. Coalescence-based divergence time estimates suggest that divergence among major clades is much more recent than previously estimated.