Wolbachia are cytoplasmically inherited bacteria that induce a variety of effects with fitness consequences on host arthropods, including cytoplasmic incompatibility, parthenogenesis, male-killing and feminization. We report here the presence of Wolbachia in native South American populations of the fire ant Solenopsis invicta, but the apparent absence of the bacteria in introduced populations of this pest species in the USA. The Wolbachia strains in native S. invicta are of two divergent types (A and B), and the frequency of infection varies dramatically between geographical regions and social forms of this host. Survey data reveal that Wolbachia also are found in other native fire ant species within the Solenopsis saevissima species complex from South America, including S. richteri. This latter species also has been introduced in the USA, where it lacks Wolbachia. Sequence data reveal complete phylogenetic concordance between mtDNA haplotype in S. invicta and Wolbachia infection type (A or B). In addition, the mtDNA and associated group A Wolbachia strain in S. invicta are more closely related to the mtDNA and Wolbachia strain found in S. richteri than they are to the mtDNA and associated group B Wolbachia in S. invicta. These data are consistent with historical introgression of S. richteri cytoplasmic elements into S. invicta populations, resulting in enhanced infection and mtDNA polymorphisms in S. invicta. Wolbachia may have significant fitness effects on these hosts (either directly or by cytoplasmic incompatibility) and therefore these microbes potentially could be used in biological control programmes to suppress introduced fire ant populations.