Virulence of Cryptococcus neoformans is regulated by a range of transcription factors, and is also influenced by the acquisition of adaptive mutations during infection. Beyond the temporal regulation of virulence factor production by transcription factors and these permanent microevolutionary changes, heritable epigenetic modifications such as histone deacetylation may also play a role during infection. Here we describe the first comprehensive analysis of the sirtuin class of NAD+ dependent histone deacetylases in the phylum Basidiomycota, identifying five sirtuins encoded in the C. neoformans genome. Each sirtuin gene was deleted and a wide range of phenotypic tests performed to gain insight into the potential roles they play. Given the pleiotropic nature of sirtuins in other species, it was surprising that only two of the five deletion strains revealed mutant phenotypes in vitro. However, cryptic consequences of the loss of each sirtuin were identified through whole cell proteomics, and mouse infections revealed a role in virulence for SIR2, HST3 and HST4. The most intriguing phenotype was the repeated inability to complement mutant phenotypes through the reintroduction of the wild-type gene. These data support the model that regulation of sirtuin activity may be employed to enable a drastic alteration of the epigenetic landscape and virulence of C. neoformans.