Shiga toxin-producing Escherichia coli (STEC) is a food-borne pathogen, where serotype O157:H7 STEC is typically associated with severe disease that can cause life-threatening illness such as haemolytic uremic syndrome. Australia is unique in its STEC epidemiology however, as severe cases are typically associated with non-O157 serogroups, and locally acquired O157 isolates are H-negative/nonmotile. The H-negative phenotype and reduced severity of disease compared to that associated with H7/motile strains are distinct features of Australian O157 strains, where the molecular mechanism behind this phenotype has not been reported. Accurate characterization of the H-negative phenotype is important in epidemiological surveillance of STEC as accurate molecular characterisation of pathogens is necessary to effectively monitor trends in infections and to identify and track sources of outbreaks, so as to enable a rapid public health response. Serotyping is moving away from phenotype-based methods, as next generation sequencing allows rapid extrapolation of serotype through in silico detection of the O-antigen processing genes, wzx, wzy, wzm, and wzt, and the H-antigen gene, fliC. The detection and genotyping of fliC alone is unable to determine the motility of the strain as most Australian O157:H-negative strains carry an H7 genotype yet phenotypically are nonmotile; thus, many are mischaracterised as H7 strains by in silico serotyping tools. Comparative genomic analysis of flagellar genes between Australian and international isolates was performed and an insertion at nucleotide (nt) 125 in the flgF gene was identified in H-negative isolates. Chi-square results showed that this insertion was significantly associated with the H-negative phenotype (P < 0.0001). Phylogenetic analysis was also completed and showed that the Australian H-negative isolates with the insertion in flgF represent a clade within the O157 serogroup, distinct from O157:H7 serotypes. This study provides a genetic target for inferring the nonmotile phenotype of Australian O157 STEC, which increases the predictive value of in silico serotyping.