Cryptococcal meningitis is a major cause of mortality throughout the developing world, yet little is known about the genetic markers underlying Cryptococcal virulence and patient outcome. We studied a cohort of 230 Cryptococcus neoformans (Cn) isolates from HIV-positive South African clinical trial patients with detailed clinical follow-up using multi-locus sequence typing and in vitro phenotypic virulence assays, correlating these data with clinical and fungal markers of disease in the patient. South African Cn displayed high levels of genetic diversity and locus variability compared to globally distributed types, and we identified 50 sequence types grouped within the main molecular types VNI, VNII and VNB, with 72% of isolates typed into one of seven 'high frequency' sequence types. Spatial analysis of patients' cryptococcal genotype was not shown to be clustered geographically, which might argue against recent local acquisition and in favour of reactivation of latent infection. Through comparison of MLST genotyping data with clinical parameters, we found a relationship between genetic lineage and clinical outcome, with patients infected with the VNB lineage having significantly worse survival (n=8, HR 3.35, CI 1.51-7.20, p=0.003), and this was maintained even after adjustment for known prognostic indicators and treatment regimen. Comparison of fungal genotype with in vitro phenotype (phagocytosis, laccase activity and CSF survival) performed on a subset of 89 isolates revealed evidence of lineage-associated virulence phenotype, with the VNII lineage displaying increased laccase activity (p=0.001) and ex vivo CSF survival (p=0.0001). These findings show that Cryptococcus neoformans is a phenotypically heterogeneous pathogen, and that lineage plays an important role in cryptococcal virulence during human infection. Furthermore, a detailed understanding of the genetic diversity in Southern Africa will support further investigation into how genetic diversity is structured across African environments, allowing assessment of the risks different ecotypes pose to infection.