Current understanding of the population genetics of free-living unicellular eukaryotes is limited, and the amount of genetic variability in these organisms is still a matter of debate. We characterized - reproductively and genetically - worldwide samples of multiple Paramecium species belonging to a cryptic species complex, Paramecium aurelia, whose species have been shown to be reproductively isolated. We found that levels of genetic diversity both in the nucleus and in the mitochondrion are substantial within groups of reproductively compatible P. aurelia strains but drop considerably when strains are partitioned according to their phylogenetic groupings. Our study reveals the existence of discrepancies between the mating behavior of a number of P. aurelia strains and their multilocus genetic profile, a controversial finding that has major consequences for both the current methods of species assignment and the species problem in the P. aurelia complex.