Many avian species endemic to Aotearoa New Zealand were driven to extinction or reduced to relict populations following successive waves of human arrival, due to hunting, habitat destruction and the introduction of mammalian predators. Among the affected species were the large flightless South Island takahē (Porphyrio hochstetteri) and the moho (North Island takahē; P. mantelli), with the latter rendered extinct and the former reduced to a single relictual population. Little is known about the evolutionary history of these species prior to their decline and/or extinction. Here we sequenced mitochondrial genomes from takahē and moho subfossils (12 takahē and 4 moho) and retrieved comparable sequence data from takahē museum skins (n = 5) and contemporary individuals (n = 17) to examine the phylogeny and recent evolutionary history of these species. Our analyses suggest that prehistoric takahē populations lacked deep phylogeographic structure, in contrast to moho, which exhibited significant spatial genetic structure, albeit based on limited sample sizes (n = 4). Temporal genetic comparisons show that takahē have lost much of their mitochondrial genetic diversity, likely due to a sudden demographic decline soon after human arrival (~750 years ago). Time-calibrated phylogenetic analyses strongly support a sister species relationship between takahē and moho, suggesting these flightless taxa diverged around 1.5 million years ago, following a single colonisation of New Zealand by a flighted Porphyrio ancestor approximately 4 million years ago. This study highlights the utility of palaeogenetic approaches for informing the conservation and systematic understanding of endangered species whose ranges have been severely restricted by anthropogenic impacts.