The motile, extremophile gram-negative bacterium Helicobacter pylori (H. pylori) colonises the human stomach in half of the world’s population and resides there for the life of the host unless treated with antibiotics. It is panmictic and analyses of its housekeeping genes (MLST genes) suggest it is weakly clonal. Previously, MLST genes have been assigned to geographic regions, and have provided clues to pre-historic migrational patterns throughout the world. We analysed the MLST genes of 113 strains isolated in Prof Marshall's clinic in Perth, Western Australia, in the context of the significant global diversity of its population. Our analysis suggests that resident H. pylori from diverse ethnic groups, recombines with the Indigenous Australian clade (coined hpSahul) in a significant proportion of patients presenting to the clinic. We hypothesise that this is most likely due to environmental sources of DNA or live bacteria recombining with the colonising bacteria. We believe this challenges the fidelity of the accepted phylogeographic classification of H. pylori.