Wolbachia bacteria are intracellular symbionts of many arthropod species. Their spread through host populations is promoted by drastic alterations imposed on their hosts' reproductive physiology. In the present study, we analyzed the association between Wolbachia strains and host mitochondrial haplotypes in a Swiss population of the ant Formica exsecta. In this species, female dispersal is extremely limited and the mitochondrial haplotypes are strongly differentiated between and within subpopulations. Our study revealed exceptionally high levels of multiple infection, with all ants harboring four or five distinct Wolbachia strains. Four of these strains were present in all ants analyzed. A fifth strain was associated with only three of the five mitochondrial haplotypes. An analysis of the Wolbachia gene wsp further revealed an unexpected high rate of recombination, with three of the five Wolbachia strains appearing to have arisen by homologous recombination.