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