In migratory animals, high mobility may reduce population structure through increased dispersal and enable adaptive responses to environmental change, whereas rigid migratory routines predict low dispersal, increased structure, and limited flexibility to respond to change. We explore the global population structure and phylogeographic history of the bar-tailed godwit, Limosa lapponica, a migratory shorebird known for making the longest non-stop flights of any landbird. Using nextRAD sequencing of 14,318 single-nucleotide polymorphisms and scenario-testing in an Approximate Bayesian Computation framework, we infer that bar-tailed godwits existed in two main lineages at the Last Glacial Maximum, when much of their present-day breeding range persisted in a vast, unglaciated Siberian-Beringian refugium, followed by admixture of these lineages in the eastern Palearctic. Subsequently, population structure developed at both longitudinal extremes: in the east, a genetic cline exists across latitude in the Alaska breeding range of subspecies L. l. baueri; in the west, one lineage diversified into three extant subspecies L. l. lapponica, taymyrensis, and yamalensis, the former two of which migrate through previously glaciated western Europe. In the global range of this long-distance migrant, we found evidence of both (1) fidelity to rigid behavioral routines promoting fine-scale geographic population structure (in the east), and (2) flexibility to colonize recently available migratory flyways and non-breeding areas (in the west). Our results suggest that cultural traditions in highly mobile vertebrates can override the expected effects of high dispersal ability on population structure, and provide insights for the evolution and flexibility of some of the world’s longest migrations.