Molecular typing methods for Burkholderia pseudomallei have been successful at assigning isolates into epidemiologically related groups, but have not been able to detect differences and define evolutionary patterns within groups. Our variable number tandem repeat (VNTR) analysis of a set of 121 Australian B. pseudomallei isolates, 104 of which were associated with nine epidemiological groups, provides fine scale differentiation even among very closely related isolates. We used a Bayesian model based upon mutation accumulation patterns to define the close phylogenetic relationships within these epidemiological groups. Our results reveal that genetic diversity can exist within a very small geographic area, and that low levels of diversity can exist even within a single infection. These methods provide the ability to generate robust evolutionary hypotheses that enable tracking of B. pseudomallei in forensic and epidemiological outbreaks at fine phylogenetic scales.