The black-spined toad, Duttaphrynus melanostictus, is widespread in South and South-East (SE) Asia, although recent molecular analyses have revealed that it represents a species complex (here called the D. melanostictus complex). Invasive populations of this toad have been detected in Madagascar since, at least, 2014. We here trace the origin of this introduction based on mitochondrial DNA sequences of 340 samples. All 102 specimens from Madagascar have identical sequences pointing to a single introduction event. Their haplotype corresponds to a lineage occurring in Cambodia, China, Laos, Thailand, Vietnam, and some locations of eastern Myanmar and northern Malaysia, here named the SE Asian lineage. Within this lineage, specimens from one location in Cambodia and three locations in Vietnam have the same haplotype as found in Madagascar. This includes Ho Chi Minh City, which has a major seaport and might have been the source for the introduction. Species distribution models suggest that the current range of the Madagascan invasive population is within the bioclimatic space occupied by the SE Asian lineage in its native range. The potential invasion zone in Madagascar is narrower than suggested by models from localities representing the full range of the D. melanostictus complex. Thus, an accurate taxonomy is essential for such inferences, but it remains uncertain if the toad might be able to spread beyond the potential suitable range because (1) knowledge on species-delimitation of the complex is insufficient, and (2) the native range in SE Asia might be influenced by historical biogeography or competition.