Past changes in population size, local population replacement, and admixture are difficult to detect based on fossils or genetic data from extant populations alone. Conversely, ancient DNA from subfossil remains allows us to directly observe these events tens-of-thousands of years in the past. North American bison (Bison sp.) have emerged as an excellent example of how ancient DNA can reveal complex population histories that are obscured by analyses of palaeontological or modern genetic data. Numerous extinct morphologically-differentiated bison species have been described from the Late Pleistocene (126 – 12 thousand years ago) of North America, including the giant long-horned bison (Bison latifrons). However, we have demonstrated that two unequivocal long-horned bison from Idaho possessed a mitochondrial lineage indistinguishable from other North American bison. This suggests either that the long-horned bison does not represent a genetically distinct species or that it underwent significant admixture with other bison taxa, calling into question both the validity of recognised bison taxa and the mechanisms driving the observed morphological variability among bison. Further, increased sampling of ancient bison individuals has revealed spatial/temporal structure in the distribution of their genetic diversity, suggesting that North American bison comprised a continent-wide metapopulation. This population structure – coupled with variable impacts of climate/environmental change at the regional level – may have contributed to the relatively depauperate genetic diversity of modern bison. The complex patterns and processes our results reveal are likely to be common across many taxa, and should influence our interpretation of results from other animal species.