Palaeognaths, the sister group of all other living birds (neognaths), were once considered to be vicariant relics from the breakup of the Gondwanan supercontinent. However, recent molecular studies instead argue for dispersal of volant ancestors across marine barriers. Resolving this debate hinges upon accurately reconstructing their evolutionary relationships and dating their divergences, which often relies on phylogenetic information from extinct relatives and nuclear genomes. Mitogenomes from the extinct elephant birds of Madagascar have helped inform the palaeognath phylogeny; however, nuclear information has remained unavailable. Here, we use ancient DNA (aDNA) extracted from fossil eggshell, together with target enrichment and next-generation sequencing techniques, to reconstruct an additional new mitogenome from Aepyornis sp. with 33.5X coverage. We also recover the first elephant bird nuclear aDNA, represented by 12,500 bp of exonic information. While we confirm that elephant birds are sister taxa to the kiwi, our data suggests that, like neognaths, palaeognaths underwent an explosive radiation between 69 and 52 Ma—well after the break-up of Gondwana, and more rapidly than previously estimated from mitochondrial data alone. These results further support the idea that ratites primarily diversified immediately following the Cretaceous-Palaeogene mass extinction and convergently evolved flightlessness. Our study reinforces the importance of including information from the nuclear genome of extinct taxa for recovering deep evolutionary relationships. Furthermore, with approximately 3% endogenous aDNA retrieved, avian eggshell can be a valuable substrate for recovering high quality aDNA. We suggest that elephant bird whole genome recovery is ultimately achievable, and will provide future insights into the evolution these birds.