Yeasts of the genus Dekkera and its anamorph Brettanomyces represent a significant spoilage issue for the global wine industry. Despite this, there is limited knowledge of genetic diversity and strain distribution within wine and winery-related environments. In this study, amplified fragment length polymorphism (AFLP) analysis was conducted on 244 Dekkera bruxellensis isolates from red wine made in 31 winemaking regions of Australia. The results indicated there were eight genotypes among the isolates, and three of these were commonly found across multiple winemaking regions. Analysis of 26S rRNA gene sequences provided further evidence of three common, conserved groups, whereas a phylogeny based upon the AFLP data demonstrated that the most common D. bruxellensis genotype (I) in Australian red wine was highly divergent from the D. bruxellensis type strain (CBS 74).