Late Quaternary climatic fluctuations in the Northern Hemisphere had drastic effects on large mammal species, leading to the extinction of a substantial number of them. The giant deer (Megaloceros giganteus) was one of the species that became extinct in the Holocene, around 7660 calendar years before present. In the Late Pleistocene, the species ranged from western Europe to central Asia. However, during the Holocene, its range contracted to eastern Europe and western Siberia, where the last populations of the species occurred. Here, we generated 35 Late Pleistocene and Holocene giant deer mitogenomes to explore the genetics of the demise of this iconic species. Bayesian phylogenetic analyses of the mitogenomes suggested five main clades for the species: three pre-Last Glacial Maximum clades that did not appear in the post-Last Glacial Maximum genetic pool, and two clades that showed continuity into the Holocene. Our study also identified a decrease in genetic diversity starting in Marine Isotope Stage 3 and accelerating during the Last Glacial Maximum. This reduction in genetic diversity during the Last Glacial Maximum, coupled with a major contraction of fossil occurrences, suggests that climate was a major driver in the dynamics of the giant deer.