Cryptococcus flavescens and C. terrestris are phenotypically indistinguishable sister species that belong to the order Tremellales (Tremellomycetes, Basidiomycota) and which may be mistaken for C. laurentii based on phenotype. Phylogenetic separation between C. flavescens and C. terrestris was based on rDNA sequence analyses, but very little is known on their intraspecific genetic variability or propensity for sexual reproduction. We studied 59 strains from different substrates and geographic locations, and used a multilocus sequencing (MLS) approach complemented with the sequencing of mating type (MAT) genes to assess genetic variation and reexamine the boundaries of the two species, as well as their sexual status. The following five loci were chosen for MLS: the rDNA ITS-LSU region, the rDNA IGS1 spacer, and fragments of the genes encoding the largest subunit of RNA polymerase II (RPB1), the translation elongation factor 1 alpha (TEF1) and the p21-activated protein kinase (STE20). Phylogenetic network analyses confirmed the genetic separation of the two species and revealed two additional cryptic species, for which the names Cryptococcus baii and C. ruineniae are proposed. Further analyses of the data revealed a high degree of genetic heterogeneity within C. flavescens as well as evidence for recombination between lineages detected for this species. Strains of C. terrestris displayed higher levels of similarity in all analysed genes and appear to make up a single recombining group. The two MAT genes (STE3 and SXI1/SXI2) sequenced for C. flavescens strains confirmed the potential for sexual reproduction and suggest the presence of a tetrapolar mating system with a biallelic pheromone/receptor locus and a multiallelic HD locus. In C. terrestris we could only sequence STE3, which revealed a biallelic P/R locus. In spite of the strong evidence for sexual recombination in the two species, attempts at mating compatible strains of both species on culture media were unsuccessful.