The systematics of Madagascar’s extinct elephant birds remains controversial due to large gaps in the fossil record and poor biomolecular preservation of skeletal specimens. Here, a molecular analysis of 1000-year-old fossil eggshells provides the first description of elephant bird phylogeography and offers insight into the ecology and evolution of these flightless giants. Mitochondrial genomes from across Madagascar reveal genetic variation that is correlated with eggshell morphology, stable isotope composition, and geographic distribution. The elephant bird crown is dated to ca. 30 Mya, when Madagascar is estimated to have become less arid as it moved northward. High levels of between-clade genetic variation support reclassifying Mullerornis into a separate family. Low levels of within-clade genetic variation suggest there were only two elephant bird genera existing in southern Madagascar during the Holocene. However, we find an eggshell collection from Madagascar’s far north that represents a unique lineage of Aepyornis. Furthermore, divergence within Aepyornis coincides with the aridification of Madagascar during the early Pleistocene ca. 1.5 Ma, and is consistent with the fragmentation of populations in the highlands driving diversification and the evolution of extreme gigantism over shorts timescales. We advocate for a revision of their taxonomy that integrates palaeogenomic and palaeoecological perspectives.