Cycles of glacial expansion and contraction throughout the Pleistocene drove increases and decreases, respectively, in the geographical range and population size of many animal species. Genetic data have revealed that during glacial maxima the distribution of many Eurasian animals was restricted to small refugial areas, from which species expanded to reoccupy parts of their former range as the climate warmed. It has been suggested that the extinct eastern moa (Emeus crassus)—a large, flightless bird from New Zealand—behaved analogously during glacial maxima, possibly surviving only in a restricted area of lowland habitat in the southern South Island of New Zealand during the Last Glacial Maximum (LGM). However, previous studies have lacked the power and geographic sampling to explicitly test this hypothesis using genetic data. Here we analyse 46 ancient mitochondrial genomes from Late Pleistocene and Holocene bones of the eastern moa from across their post-LGM distribution. Our results are consistent with a post-LGM increase in the population size and genetic diversity of eastern moa. We also demonstrate that genetic diversity was higher in eastern moa from the southern extent of their range, supporting the hypothesis that they expanded from a single glacial refugium following the LGM.