Wolbachia are maternally inherited endosymbiotic bacteria that infect many arthropod species and may induce cytoplasmic incompatibility (CI), resulting in abortive embryonic development. One Wolbachia host, Culex pipiens complex mosquitoes, displays high levels of variability in both CI crossing types (cytotypes) and DNA markers. We report here an analysis of 14 mosquito strains, containing 13 Wolbachia variants, and with 13 different cytotypes. Cytotypes were Wolbachia-dependent, as antibiotic treatment rendered all strains tested compatible. Cytotype distributions were independent of geographical distance between sampling sites and host subspecies, suggesting that Wolbachia does not promote a reproductive isolation depending on these parameters. Backcross analysis demonstrated a mild restoring effect of the nuclear genome, indicating that CI is mostly cytoplasmically determined for some crosses. No correlation was found between the phenotypic and genotypic variability of 16 WO prophage and transposon markers, except for the WO prophage Gp15 gene, which encodes a protein similar to a bacterial virulence factor. However, Gp15 is partially correlated with CI expression, suggesting that it could be just linked to a CI gene.