Wolbachia are common endosymbiotic bacteria of Arthropoda and Nematoda that are ordinarily transmitted vertically in host lineages through the egg cytoplasm. Despite the great interest in the Wolbachia symbiont, many issues of its biology remain unclear, including its evolutionary history, routes of transfer among species, and the molecular mechanisms underlying the symbiont's effect on its host. In this report, we present data relating to Wolbachia infection in 120 species of 13 Lepidoptera families, mostly butterflies, from West Siberian localities based on Multilocus sequence typing (MLST) and the wsp locus and perform a comprehensive survey of the distribution of Wolbachia and its genetic diversity in Lepidoptera worldwide. We observed a high infection incidence in the studied region; this finding is probably also true for other temperate latitude regions because many studied species have broad Palearctic and even Holarctic distribution. Although 40 new MLST alleles and 31 new STs were described, there was no noticeable difference in the MLST allele content in butterflies and probably also in moths worldwide. A genetic analysis of Wolbachia strains revealed the MLST allele core in lepidopteran hosts worldwide, viz. the ST-41 allele content. The key finding of our study was the detection of rampant recombination among MLST haplotypes. High rates of homologous recombination between Wolbachia strains indicate a substantial contribution of genetic exchanges to the generation of new STs. This finding should be considered when discussing issues related to the reconstruction of Wolbachia evolution, divergence time, and the routes of Wolbachia transmission across arthropod hosts.