Madagascar is home to many endemic plant and animal species owing to its ancient isolation from other landmasses. This unique fauna includes several lineages of termites, a group of insects known for their key role in organic matter decomposition in many terrestrial ecosystems. How and when termites colonized Madagascar remains unknown. In this study, we used 601 mitochondrial genomes, 93 of which were generated from Malagasy samples, to infer the global historical biogeography of Neoisoptera, a lineage containing upwards of 80% of described termite species. Our results indicate that Neoisoptera colonized Madagascar between seven to ten times independently during the Miocene, between 8.4-16.6 Ma (95% HPD: 6.1-19.9 Ma). This timing matches that of the colonization of Australia by Neoisoptera. Furthermore, the taxonomic composition of the Neoisopteran fauna of Madagascar and Australia are strikingly similar, with Madagascar harboring an additional two lineages absent from Australia. Therefore, akin to Australia, Neoisoptera colonized Madagascar during the global expansion of grasslands, possibly helped by the ecological opportunities arising from the spread of this new biome.