Wolbachia are intracellular bacteria that induce phenotypic effects in many arthropod hosts to enhance their own spread within host populations. Wolbachia commonly infect the Red Imported Fire Ant, Solenopsis invicta, in its native South American range, but a previous study failed to detect Wolbachia in fire ants from the introduced range in the U.S.A. We conducted an extensive survey of individuals collected from 1157 nests from ten widespread geographic populations in the U.S.A. We found Wolbachia in ants from two nearby populations in southern Mississippi, and, surprisingly, different variants (based on wsp) infecting ants from polygyne versus monogyne colonies. The parsimonious explanation for the presence of Wolbachia in introduced S. invicta is that there have been one or more recent introductions of Wolbachia-infected fire ants into the southern U.S.A.