Burkholderia pseudomallei is the environmental bacillus that causes melioidosis; a disease clinically significant in Australia and Southeast Asia but emerging in tropical and sub-tropical regions around the globe. Previous studies have placed the ancestral population of the organism in Australia with a single lineage disseminated to Southeast Asia. We have previously characterized B. pseudomallei isolates from New Guinea and the Torres Strait archipelago; remote regions that share paleogeographic ties with Australia. These studies identified regional biogeographical boundaries. In this study, we utilize whole-genome sequencing to reconstruct ancient evolutionary relationships and ascertain correlations between paleogeography and present-day distribution of this bacterium in Australasia. Our results indicate that B. pseudomallei from New Guinea fall into a single clade within the Australian population. Furthermore, clades from New Guinea are region-specific; an observation possibly linked to limited recent anthropogenic influence in comparison to mainland Australia and Southeast Asia. Isolates from the Torres Strait archipelago were distinct yet scattered among those from mainland Australia. These results provide evidence that the New Guinean and Torres Strait lineages May be remnants of an ancient portion of the Australian population. Rising sea levels isolated New Guinea and the Torres Strait Islands from each other and the Australian mainland, and May have allowed long-term isolated evolution of these lineages, providing support for a theory of microbial biogeography congruent with that of macro flora and fauna. Moreover, these findings indicate that contemporary microbial biogeography theories should consider recent and ongoing impacts of globalisation and human activity.