The genomic study of specimens dating to the Early and Middle Pleistocene (EP and MP), a period spanning from 2.6 million years ago (Ma) to 126 thousand years ago (ka), has the potential to elucidate the evolutionary processes that shaped present-day biodiversity. Obtaining genomic data from this period is challenging, but mitochondrial DNA, given its higher abundance compared to nuclear DNA, could play an important role to understand evolutionary processes at this time scale. In this study, we report 34 new mitogenomes, including two EP and nine MP mammoth (Mammuthus spp.) specimens from Siberia and North America and analyze them jointly with >200 publicly available mitogenomes to reconstruct a transect of mammoth mitogenome diversity throughout the last million years. We find that our EP mitogenomes fall outside the diversity of all Late Pleistocene (LP) mammoths, while those derived from MP mammoths are basal to LP mammoth Clades 2 and 3, supporting an ancient Siberian origin of these lineages. In contrast, the geographical origin of Clade 1 remains unresolved. With these new deep-time mitogenomes, we observe diversification events across all clades that appear consistent with previously hypothesized MP and LP demographic changes. Furthermore, we improve upon an existing methodology for molecular clock dating of specimens >50 ka, demonstrating that specimens need to be individually dated to avoid biases in their age estimates. Both the molecular and analytical improvements presented here highlight the importance of deep-time genomic data to discover long-lost genetic diversity, enabling better assessments of evolutionary histories.