Wolbachia are intracellular maternally inherited alpha-Proteobacteria infecting a wide range of arthropods. In the common pill bug Armadillidium vulgare, the known Wolbachia strain is responsible for feminization of genetic males. We have investigated Wolbachia diversity in 20 populations of A. vulgare from west and east Europe, north Africa and north America. A new Wolbachia strain (wVulM) was identified through the variability of the wsp gene, distantly related to that previously known (wVulC) in this host species. No individual with multiple infections was detected. Inoculation experiments indicated that the new wVulM bacterial strain also induces feminization in A. vulgare. However, the wVulC strain showed a higher transmission rate than the wVulM strain and was the most geographically widespread Wolbachia in A. vulgare populations. Mitochondrial 16SrDNA gene sequencing was conducted in Wolbachia-infected individuals, revealing the occurrence of four host lineages. The comparison of bacterial strains and their respective host mitochondrial phylogenies failed to show concordance, indicating horizontal transmission of the Wolbachia strains within populations of A. vulgare.