Background: The Lysiphlebus fabarum group is a taxonomically poorly resolved complex of aphid parasitoids, presently split into three described species that comprise sexual (arrhenotokous) and asexual (thelytokous) lineages of unknown relationship. Specifically, it is unclear how asexuals evolved from sexuals in this system, to what extent reproductive modes are still connected by genetic exchange, how much the complex is structured by geography or by host-associated differentiation, and whether species designations are valid. Using a combination of population genetic and phylogenetic approaches, we addressed these issues in a comprehensive sample of parasitoid wasps from across Europe. Results: Asexual reproduction predominated in parasitoids of the L. fabarum group, with asexual populations exhibiting high genotypic diversity. Sexual populations were only common in southern France; elsewhere sexual reproduction was restricted to specific aphid hosts. Although reproductive modes were aggregated on the mitochondrial genealogy and significantly differentiated at nuclear microsatellite loci, there was clear evidence for genetic exchange, especially on hosts attacked by sexual and asexual parasitoids. The microsatellite data further revealed that parasitoids collected from certain host aphids were significantly differentiated, yet the mitochondrial sequence variation across the entire L. fabarum group did not exceed 1.32% and exhibited a very shallow topology. Morphological characters used for delineation of described species were found to be phylogenetically non-conservative. Conclusions: Our results suggest that the sexual-asexual L. fabarum group represents a young complex of lineages with incomplete isolation between reproductive modes. We propose three mechanisms of genetic exchange that may jointly explain the high genotypic diversity observed in asexual parasitoids: (i) the formation of new asexual lineages via `contagious parthenogenesis', (ii) introgression from sexual lineages through matings between sexual males and thelytokous females, and (iii) `cryptic sex' within asexuals, mediated by rare males that thelytokous lines are known to produce spontaneously. The partially strong differentiation among wasps collected from different aphids suggests that host specialization can evolve readily in these parasitoids. Finally, we conclude that in the light of our data, the current taxonomic division of the L. fabarum group into three species cannot be upheld.