The blood-feeding cosmopolitan stable fly, Stomoxys calcitrans L. (Diptera: Muscidae), is thought to disperse rapidly and widely, and earlier studies of allozyme variation were consistent with high vagility in this species. The geographic origins of New World populations are unknown. Diversity at mitochondrial loci r16S and cytochrome oxidase I was examined in 277 stable flies from 11 countries, including five zoogeographical regions. Of 809 nucleotides, 174 were polymorphic and 133 were parsimony informative. Seventy-six haplotypes were found in frequencies consistent with the Wright–Fisher infinite allele model. None were shared among four or more zoogeographical regions. The null hypothesis of mutation neutrality was not rejected, thereby validating the observed distribution. Fifty-nine haplotypes were singular, eight were private and confined to the Old World, and three of 76 haplotypes were shared between the Old and New World. Only 19 haplotypes were found in the New World, 14 of which were singletons. Haplotype and nucleotide diversities were heterogeneous among countries and regions. The most diversity was observed in sub-Saharan Africa. Regional differentiation indices were GRT = 0.26 and NRT = 0.31, indicating populations were highly structured macrogeographically. Palearctic and New World flies were the least differentiated from each other. There were strong genetic similarities among populations in the Nearctic, Neotropical, and Palearctic regions, and it is most likely that New World populations were derived from the Palearctic after 1492 CE, in the colonial era.