Escherichia coli O157:H7, a toxin-producing food and waterborne bacterial pathogen, has been linked to large outbreaks of gastrointestinal illness for more than two decades. E. coli O157 causes a wide range of clinical illness that varies by outbreak, although factors that contribute to variation in disease severity are poorly understood. Several recent outbreaks involving O157 contamination of fresh produce (e.g., spinach) were associated with more severe disease, as defined by higher hemolytic uremic syndrome and hospitalization frequencies, suggesting that increased virulence has evolved. To test this hypothesis, we developed a system that detects SNPs in 96 loci and applied it to >500 E. coli O157 clinical strains. Phylogenetic analyses identified 39 SNP genotypes that differ at 20% of SNP loci and are separated into nine distinct clades. Differences were observed between clades in the frequency and distribution of Shiga toxin genes and in the type of clinical disease reported. Patients with hemolytic uremic syndrome were significantly more likely to be infected with clade 8 strains, which have increased in frequency over the past 5 years. Genome sequencing of a spinach outbreak strain, a member of clade 8, also revealed substantial genomic differences. These findings suggest that an emergent subpopulation of the clade 8 lineage has acquired critical factors that contribute to more severe disease. The ability to detect and rapidly genotype O157 strains belonging to such lineages is important and will have a significant impact on both disease diagnosis and treatment guidelines.