Melioidosis is caused by the gram-negative saprophytic bacterium Burkholderia pseudomallei, which is endemic to southeast Asia and northern Australia. We have previously found evidence of geographic localization of strains based on multilocus sequence typing (MLST). In this study, we examined the diversity of 277 isolates from northern Australia, which were resolved into 159 different sequence types. No sequence types were common to both Queensland and the Northern Territory, and there was significant differentiation between the alleles present in the two regions. The considerable diversity in sequence types contrasts with the limited diversity of alleles at MLST loci, supporting previous work suggesting a high rate of recombination relative to mutation in B. pseudomallei, where new sequence types are primarily generated by reassortment of existing alleles.