Wolbachia are intracellular symbiotic bacteria of terrestrial arthropods and some nematodes. They are found in most insect orders; however, there are insufficient data on symbiont distribution patterns for some taxonomic groups. Here we examined a collection of Siphonaptera species by conventional and nested PCR. A total of 722 specimens from 30 species were sampled in three regions of Russia: Southern Russia, the Urals, and the Far East. Wolbachia infection was found in half of the species, which confirmed previous data on widespread of the infection in Siphonaptera. No statistical differences in Wolbachia incidence in flea species from Southern Russia and the Far East were detected, although species lists of these regions completely differed. We did not find totally infected flea species, although high infection rates were detected for Frontopsylla elata botis (64.5%) and Ctenophthalmus wagneri (66%) with sample size exceeding 30 specimens. Our results are in agreement with the data from other regions of the world. Combined data of our study and other authors indicate that Wolbachia symbionts are found in all eleven studied families of Siphonaptera and in 45 out of about 120 studied species in the world.