The evolution of the ratite birds has been widely attributed to vicariant speciation, driven by the Cretaceous breakup of the supercontinent Gondwana. The early isolation of Africa and Madagascar implies that the ostrich and extinct Madagascan elephant birds (Aepyornithidae) should be the oldest ratite lineages. We sequenced the mitochondrial genomes of two elephant birds and performed phylogenetic analyses, which revealed that these birds are the closest relatives of the New Zealand kiwi and are distant from the basal ratite lineage of ostriches. This unexpected result strongly contradicts continental vicariance and instead supports flighted dispersal in all major ratite lineages. We suggest that convergence toward gigantism and flightlessness was facilitated by early Tertiary expansion into the diurnal herbivory niche after the extinction of the dinosaurs.