Pleistocene population dynamics can inform the consequences of current climate change. This phylogeography of 35 complete American mastodon mitochondrial genomes suggests distinct lineages in this species repeatedly expanded northwards and then went locally extinct in response to glacial cycles.