Abstract Background Mosquitoes of the Culex pipiens complex are cosmopolitan, and important vectors of neglected tropical diseases, such as arbovirosis and lymphatic filariasis. Among the complex taxa, Cx. pipiens (with two forms pipiens and molestus) and Cx. quinquefasciatus are the most ubiquitous mosquitoes in temperate and tropical regions respectively. Mosquitoes of this taxa lack of morphological differences between females, but have frank behavioral and physiological differences and have different trophic preferences that influence their vectorial status. Hybridization may change the vectorial capacity of these mosquitoes, increasing vector efficiency and medical importance of resulting hybrids. Methods Culex pipiens s.l. from 35 distinct populations were investigated by the study of mtDNA, symbiotic bacterium Wolbachia pipientis, nuclear DNA and flanking region of microsatellite CQ11 polymorphism using PCR with diagnostic primers, RFLP analysis and sequencing. Results Six different mitochondrial haplotypes were revealed by sequencing of the cytochrome oxidase subunit I (COI) gene and three different Wolbachia (wPip) groups were identified. A strong association was observed between COI haplotypes/groups, wPip groups and taxa; haplogroup A and infection with wPipII appear to be typical for Cx. pipiens form pipiens, haplotype D and infection with wPipIV for form molestus, while haplogroup E, characteristic of Cx. quinquefasciatus, were correlated with wPipI and found in Cx. pipiens sl. from coastal regions of Southern Europe and Mediterranean region. Analysis of microsatellite locus and nuclear DNA revealed hybrids between Cx. pipiens form pipiens and form molestus, as well as between Cx. pipiens and Cx. quinquefasciatus, in Mediterranean populations, as opposed to Northern Europe. Phylogenetic analysis of COI sequences yielded a tree topology that supported the RFLP analysis with significant bootstrap values for haplotype D and haplogroup E. Conclusions Molecular identification provides the first evidence of the presence of hybrids between Cx. quinquefasciatus and Cx. pipiens as well as cytoplasmic introgression of Cx. quinquefasciatus into Cx. pipiens as a result of hybridization events in coastal regions of Southern Europe and Mediterranean region. Together with observed hybrids between pipiens and molestus forms, these findings point to the presence of hybrids in these areas, with consequent higher potential for disease transmission.