Present-day ecology and population structure are the legacies of past climate and habitat perturbations, and this is particularly true for species that are widely distributed at high latitudes. The red knot, Calidris canutus, is an arctic-breeding, long-distance migratory shorebird with six recognized subspecies defined by differences in morphology, migration behavior, and annual-cycle phenology, in a global distribution thought to have arisen just since the Last Glacial Maximum (LGM). We used nextRAD sequencing of 10,881 single-nucleotide polymorphisms (SNPs) to assess the neutral genetic structure and phylogeographic history of 172 red knots representing all known global breeding populations. Using population genetics approaches, including model-based scenario-testing in an approximate Bayesian computation (ABC) framework, we infer that red knots derive from two main lineages that diverged ca. 34,000 years ago, and thus persisted at the LGM in both Palearctic and Nearctic refugia, followed by at least two instances of secondary contact and admixture. In two flyways, we detected clear genetic structure between population pairs with similar migrations and substantial geographic overlap in the non-breeding season. Conversely, other populations were only weakly differentiated despite clearly divergent migratory phenotypes and little or no apparent contact throughout the annual cycle. In general, the magnitude of genetic differentiation did not match that of phenotypic differences among populations, suggesting that flyway-specific phenotypes developed quite rapidly and do not necessarily impose barriers to gene flow. Our results suggest that population structure and migratory phenotypes in red knots arose from a complex interplay among phylogeography, plasticity, and selective processes.