Background: Cryptococcus gattii is a basidiomycetous yeast that causes life-threatening disease in humans and animals. Within C. gattii, four molecular types are recognized (VGI to VGIV). The Australian VGII population has been in the spotlight since 2005, when it was suggested as the possible origin for the ongoing outbreak at Vancouver Island (British Columbia, Canada), with same-sex mating being suggested as the driving force behind the emergence of this outbreak, and is nowadays hypothesized as a widespread phenomenon in C. gattii. However, an in-depth characterization of the Australian VGII population is still lacking. The present work aimed to define the genetic variability within the Australian VGII population and determine processes shaping its population structure. Methodology/Principal Findings: A total of 54 clinical, veterinary and environmental VGII isolates from different parts of the Australian continent were studied. To place the Australian population in a global context, 17 isolates from North America, Europe, Asia and South America were included. Genetic variability was assessed using the newly adopted international consensus multi-locus sequence typing (MLST) scheme, including seven genetic loci: CAP59, GPD1, LAC1, PLB1, SOD1, URA5 and IGS1. Despite the overall clonality observed, the presence of MATa VGII isolates in Australia was demonstrated for the first time in association with recombination in MATα-MATa populations. Our results also support the hypothesis of a "smouldering" outbreak throughout the Australian continent, involving a limited number of VGII genotypes, which is possibly caused by a founder effect followed by a clonal expansion. Conclusions/Significance: The detection of sexual recombination in MATα-MATa population in Australia is in accordance with the natural life cycle of C. gattii involving opposite mating types and presents an alternative to the same-sex mating strategy suggested elsewhere. The potential for an Australian wide outbreak highlights the crucial issue to develop active surveillance procedures.