American bison demonstrated differential patterns of extinction, survival, and expansion since the terminal Pleistocene. We determined population dynamics of the Northern Great Plains bison using 40 mitochondrial genomes from radiocarbon dated remains with the age ranging from 12,226 to 167 calibrated years before present. Population dynamics correlated with environmental and anthropogenic factors and was characterized by three primary periods: terminal Pleistocene population growth starting 14,000 years ago, mid Holocene demographic stability between 6700 and 2700 years ago, and late Holocene population decline in the last 2700 years. Most diversification of mtDNA haplotypes occurred in the early Holocene when bison colonized new territories opened by retreating ice sheets. Holocene mtDNA lineages were not found in modern bison and lacked association with archaeological sites and morphological forms.