New Zealand offers a unique opportunity to investigate the response of extinct megafaunal ecosystems to major changes in climate and habitat prior to human settlement. Prior to this point (late 13th Century AD) New Zealand contained a diverse avian megafauna dominated by nine species of large flightless ratite moa (Dinornithiformes). We used ancient DNA approaches to generate mitochondrial DNA sequence data from 39 crested moa (Pachyornis australis) and 145 heavy-footed moa (Pachyornis elephantopus) specimens. In combination with radiocarbon dating and dietary isotope analysis we examined the effects of Late Pleistocene and Holocene climate and environmental change on the phylogeography, palaeodemographics, and eventual extinction of Pachyornis. We show that Pachyornis changed altitudinal, longitudinal and latitudinal ranges through the Late Quaternary in response to alterations in the distribution of suitable habitat. However, we found no evidence for large-scale change in population sizes during the past 40,000 radiocarbon years BP (approximately 44,000 calendar years BP), or significant changes in δ ¹³C and δ ¹⁵N isotope signatures over this time period. The results suggest that crested moa tracked habitat through time with little consequence to population size. For the more broadly distributed heavy-footed moa, changes in climate and habitat distribution may have promoted phylogeographic structuring. Overall this study suggests that the likelihood of megafaunal extinction in New Zealand was greatly reduced in the absence of humans.