Background: Maternally inherited Wolbachia symbionts infect D. melanogaster populations worldwide. Infection rates vary greatly. Genetic diversity of Wolbachia in D. melanogaster can be subdivided into several closely related genotypes coinherited with certain mtDNA lineages. mtDNA haplotypes have the following global distribution pattern: mtDNA clade I is mostly found in North America, II and IV in Africa, III in Europe and Africa, V in Eurasia, VI is global but very rare, and VIII is found in Asia. The wMel Wolbachia genotype is predominant in D. melanogaster populations. However, according to the hypothesis of global Wolbachia replacement, the wMelCS genotype was predominant before the XX century when it was replaced by the wMel genotype. Here we analyse over 1500 fly isolates from the Palearctic region to evaluate the prevalence, genetic diversity and distribution pattrern of the Wolbachia symbiont, occurrence of mtDNA variants, and finally to discuss the Wolbachia genotype global replacement hypothesis. Results: All studied Palearctic populations of D. melanogaster were infected with Wolbachia at a rate of 33-100%. We did not observe any significant correlation between infection rate and longitude or latitude. Five previously reported Wolbachia genotypes were found in Palearctic populations with a predominance of the wMel variant. The mtDNA haplotypes of the I-II-III clade and V clade were prevalent in Palearctic populations. To test the recent Wolbachia genotype replacement hypothesis, we examined three genomic regions of CS-like genotypes. Low genetic diversity was observed, only two haplotypes of the CS genotypes with a 'CCG' variant predominance were found. Conclusion: The results of our survey of Wolbachia infection prevalence and genotype diversity in Palearctic D. melanogaster populations confirm previous studies. Wolbachia is ubiquitous in the Palearctic region. The wMel genotype is dominant with local occurrence of rare genotypes. Together with variants of the V mtDNA clade, the variants of the 'III+' clade are dominant in both infected and uninfected flies of Palearctic populations. Based on our data on Wolbachia and mtDNA in different years in some Palearctic localities, we can conclude that flies that survive the winter make the predominant symbiont contribution to the subsequent generation. A comprehensive overview of mtDNA and Wolbachia infection of D. melanogaster populations worldwide does not support the recent global Wolbachia genotype replacement hypothesis. However, we cannot exclude wMelCS genotype rate fluctuations in the past.