Understanding the phylogeographic history of an invasive species may facilitate reconstructing the history and routes of its invasion. The longhorn crazy ant, Paratrechina longicornis, is a ubiquitous agricultural and household pest throughout much of the tropics and subtropics, but little is known about the history of its spread. Here, we examine worldwide genetic variation in P. longicornis and its associated Wolbachia bacterial symbionts. Analyses of mtDNA sequences of 248 P. longicornis workers (one per colony) from 13 geographic regions reveal two highly diverged mtDNA clades that co-occur in most of the geographic regions. These two mtDNA clades are associated with different Wolbachia infection patterns, but are not congruent with patterns of nDNA (microsatellite) variation. Multilocus sequence typing reveals two distinct Wolbachia strains in P. longicornis, namely, wLonA and wLonF. The evolutionary histories of these two strains differ; wLonA appears to be primarily transmitted maternally, and patterns of mtDNA and nDNA variation and wLonA infection status are consistent with a relatively recent Wolbachia-induced selective sweep. In contrast, the observed patterns of mtDNA variation and wLonF infections suggest frequent horizontal transfer and losses of wLonF infections. The lack of nDNA structure among sampled geographic regions coupled with the finding that numerous mtDNA haplotypes are shared among regions implies that inadvertent long-distance movement through human commerce is common in P. longicornis and has shaped the genetic structure of this invasive ant worldwide.