Escherichia coli O157 is a food-borne pathogen whose major reservoir has been identified as cattle. Recent genetic information has indicated that populations of E. coli O157 from cattle and humans can differ genetically and that this variation may have an impact on their ability to cause severe human disease. In addition, there is emerging evidence that E. coli O157 strains from different geographical regions may also be genetically divergent. To investigate the extent of this variation, we used Shiga toxin bacteriophage insertion sites (SBI), lineage-specific polymorphisms (LSPA-6), multilocus variable-number tandem-repeat analysis (MLVA), and a tir 255T>A polymorphism to examine 606 isolates representing both Australian and U.S. cattle and human populations. Both uni- and multivariate analyses of these data show a strong association between the country of origin and multilocus genotypes (P < 0.0001). In addition, our results identify factors that may play a role in virulence that also differed in isolates from each country, including the carriage of stx1 in the argW locus uniquely observed in Australian isolates and the much higher frequency of stx2-positive (also referred to as stx2a) strains in the U.S. isolates (4% of Australian isolates versus 72% of U.S. isolates). LSPA-6 lineages differed between the two continents, with the majority of Australian isolates belonging to lineage I/II (LI/II) (LI, 2%; LI/II, 85%; LII, 13%) and the majority of U.S. isolates belonging to LI (LI, 60%; LI/II, 16%; LII, 25%). The results of this study provide strong evidence of phylogeographic structuring of E. coli O157 populations, suggesting divergent evolution of enterohemorrhagic E. coli O157 in Australia and the United States.