Many mosquitoes harbour Wolbachia symbionts that could affect the biology of their host in different ways. Evolutionary relationships of mosquitoes’ Wolbachia infection, geographical distribution and symbiont prevalence in many mosquito species are not yet clear. Here, we present the results of Wolbachia screening of 17 mosquito species of four genera—Aedes, Anopheles, Coquillettidia and Culex collected from five regions of Eastern Europe and the Caucasus in 2012–2016. Based on multilocus sequence typing (MLST) data previously published and generated in this study, we try to reveal genetic links between mosquitoes’ and other hosts’ Wolbachia. The Wolbachia symbionts are found in Culex pipiens, Aedes albopictus and Coquillettidia richiardii and for the first time in Aedes cinereus and Aedes cantans, which are important vectors of human pathogens. Phylogenetic analysis demonstrated multiple origins of infection in mosquitoes although the one-allele-criterion approach revealed links among B-supergroup mosquito Wolbachia with allele content of lepidopteran hosts. The MLST gene content of strain wAlbA from the A-supergroup is linked with different ant species. Several cases of intersupergroup recombinations were found. One of them occurred in the wAlbaB strain of Aedes albopictus, which contains the coxA allele of the A-supergroup, whereas other loci, including wsp, belong to supergroup B. Other cases are revealed for non-mosquito symbionts and they exemplified genetic exchanges of A, B and F supergroups. We conclude that modern Wolbachia diversity in mosquitoes and in many other insect taxa is a recent product of strain recombination and symbiont transfers.