Wolbachia are endosymbiotic bacteria known to manipulate the reproduction of their hosts. These manipulations are expected to have consequences on the population genetics of the host, such as heterozygosity levels, genetic diversity and gene flow. The parasitoid wasp Tetrastichus coeruleus has populations that are infected with parthenogenesis-inducing Wolbachia and populations that are not infected. We studied the population genetics of T. coeruleus between and within Wolbachia-infected and uninfected populations, using nuclear microsatellites and mitochondrial DNA. We expected reduced genetic diversity in both DNA types in infected populations. However, migration and gene flow could introduce new DNA variants into populations. We therefore paid special attention to individuals with unexpected (genetic) characteristics. Based on nuclear and mitochondrial DNA, two genetic clusters were evident: a thelytokous cluster containing all Wolbachia-infected, parthenogenetic populations and an arrhenotokous cluster containing all uninfected, sexual populations. Nuclear and mitochondrial DNA did not exhibit concordant patterns of variation, although there was reduced genetic diversity in infected populations for both DNA types. Within the thelytokous cluster, there was nuclear DNA variation, but no mitochondrial DNA variation. This nuclear DNA variation may be explained by occasional sex between infected females and males, by horizontal transmission of Wolbachia, and/or by novel mutations. Several females from thelytokous populations were uninfected and/or heterozygous for microsatellite loci. These unexpected characteristics may be explained by migration, by inefficient transmission of Wolbachia, by horizontal transmission of Wolbachia, and/or by novel mutations. However, migration has not prevented the build-up of considerable genetic differentiation between thelytokous and arrhenotokous populations.