Background Wolbachia are endosymbiotic bacteria that commonly infect numerous arthropods. Despite their broad taxonomic distribution, the transmission patterns of these bacteria within and among host species are not well understood. We sequenced a portion of the wsp gene from the Wolbachia genome infecting 138 individuals from eleven geographically distributed native populations of the fire ant Solenopsis invicta. We then compared these wsp sequence data to patterns of mitochondrial DNA (mtDNA) variation of both infected and uninfected host individuals to infer the transmission patterns of Wolbachia in S. invicta. Results Three different Wolbachia (wsp) variants occur within S. invicta, all of which are identical to previously described strains in fire ants. A comparison of the distribution of Wolbachia variants within S. invicta to a phylogeny of mtDNA haplotypes suggests S. invicta has acquired Wolbachia infections on at least three independent occasions. One common Wolbachia variant in S. invicta (wSinvictaB) is associated with two divergent mtDNA haplotype clades. Further, within each of these clades, Wolbachia-infected and uninfected individuals possess virtually identical subsets of mtDNA haplotypes, including both putative derived and ancestral mtDNA haplotypes. The same pattern also holds for wSinvictaA, where at least one and as many as three invasions into S. invicta have occurred. These data suggest that the initial invasions of Wolbachia into host ant populations may be relatively ancient and have been followed by multiple secondary losses of Wolbachia in different infected lineages over time. Finally, our data also provide additional insights into the factors responsible for previously reported variation in Wolbachia prevalence among S. invicta populations. Conclusion The history of Wolbachia infections in S. invicta is rather complex and involves multiple invasions or horizontal transmission events of Wolbachia into this species. Although these Wolbachia infections apparently have been present for relatively long time periods, these data clearly indicate that Wolbachia infections frequently have been secondarily lost within different lineages. Importantly, the uncoupled transmission of the Wolbachia and mtDNA genomes suggests that the presumed effects of Wolbachia on mtDNA evolution within S. invicta are less severe than originally predicted. Thus, the common concern that use of mtDNA markers for studying the evolutionary history of insects is confounded by maternally inherited endosymbionts such as Wolbachia may be somewhat unwarranted in the case of S. invicta.