The Cryptococcus species complex contains two sibling taxa, Cryptococcus neoformans and Cryptococcus gattii. Both species are basidiomycetous yeasts and major pathogens of humans and other mammals. Genotyping methods have identified major haploid molecular types of C. neoformans (VNI, VNII, VNB and VNIV) and of C. gattii (VGI, VGII, VGIII and VGIV). To investigate the phylogenetic relationships among these haploid genotypes, we selected 73 strains from 2000 globally collected isolates investigated in our previous typing studies, representing each of these genotypes and carried out multigene sequence analyses using four genetically unlinked nuclear loci, ACT1, IDE, PLB1 and URA5. The separate or combined sequence analyses of all four loci revealed seven clades with significant support for each molecular type. However, three strains of each species revealed some incongruence between the original molecular type and the sequence-based type obtained here. The topology of the individual gene trees was identical for each clade of C. neoformans but incongruent for the clades of C. gattii indicating recent recombination events within C. gattii. There was strong evidence of recombination in the global VGII population. Both parsimony and likelihood analyses supported three major clades of C. neoformans (VNI/VNB, VNII and VNIV) and four major clades of C. gattii (VGI, VGII, VGIII and VGIV). The sequence variation between VGI, VGIII and VGIV was similar to that between VNI/VNB and VNII. MATa was for the first time identified for VGIV. The VNIV and VGII clades are basal to the C. neoformans or the C. gattii clade, respectively. Divergence times among the seven haploid monophyletic lineages in the Cryptococcus species complex were estimated by applying the hypothesis of the molecular clock. The genetic variation found among all of these haploid monophyletic lineages indicates that they warrant varietal status.