Cryptococcosis caused by yeasts of the Cryptococcus gattii species complex is an increasingly important mycological disease in humans and other mammals. In Australia, cases of C. gattii-related cryptococcosis are more prevalent in the koala (Phascolarctos cinereus) compared to humans and other animals, likely due to the close association that both C. gattii and koalas have with Eucalyptus species. This provides a cogent opportunity to investigate the epidemiology of spontaneous C. gattii infections in a free-living mammalian host, thereby offering insights into similar infections in humans. This study aimed to establish a link between nasal colonisation by C. gattii in free-ranging koalas and the tree hollows of Eucalyptus species, the key environmental source of the pathogen. We (i) detected and genotyped C. gattii from nine out of 169 free-ranging koalas and representative tree hollows within their home range in the Liverpool Plains, New South Wales, and (ii) examined potential environmental predictors of nasal colonisation in koalas and the presence of C. gattii in tree hollows. Phylogenetic analyses based on multi-locus sequence typing (MLST) revealed that the koalas were most likely colonised by the most abundant C. gattii genotypes found in the Eucalyptus species, or closely related genotypes. Importantly, the likelihood of the presence of C. gattii in tree hollows was correlated with increasing hollow size.