The New Zealand acanthisittid wrens are the sister-taxon to all other “perching birds” (Passeriformes) and – including recently extinct species – represent the most diverse endemic passerine family in New Zealand. Consequently, they are important for understanding both the early evolution of Passeriformes and the New Zealand biota. However, five of the seven species have become extinct since the arrival of humans in New Zealand, complicating evolutionary analyses. The results of morphological analyses have been largely equivocal, and no comprehensive genetic analysis of Acanthisittidae has been undertaken. We present novel mitochondrial genome sequences from four acanthisittid species (three extinct, one extant), allowing us to resolve the phylogeny and revise the taxonomy of acanthisittids. Reanalysis of morphological data in light of our genetic results confirms a close relationship between the extant rifleman (Acanthisitta chloris) and an extinct Miocene wren (Kuiornis indicator), making Kuiornis a useful calibration point for molecular dating of passerines. Our molecular dating analyses reveal that the stout-legged wrens (Pachyplichas) diverged relatively recently from a more gracile (Xenicus-like) ancestor. Further, our results suggest a possible Early Oligocene origin of the basal Lyall’s wren (Traversia) lineage, which would imply that Acanthisittidae survived the Oligocene marine inundation of New Zealand and therefore that the inundation was not complete.