We used whole-genome sequencing to investigate the evolutionary context of an emerging highly pathogenic strain of Shiga toxin-producing Escherichia coli (STEC) O157:H7 in England and Wales. A timed phylogeny of sublineage IIb revealed that the emerging clone evolved from a STEC O157:H7 stx-negative ancestor ≈10 years ago after acquisition of a bacteriophage encoding Shiga toxin (stx) 2a, which in turn had evolved from a stx2c progenitor ≈20 years ago. Infection with the stx2a clone was a significant risk factor for bloody diarrhea (OR 4.61, 95% CI 2.24-9.48; p<0.001), compared with infection with other strains within sublineage IIb. Clinical symptoms of cases infected with sublineage IIb stx2c and stx-negative clones were comparable, despite the loss of stx2c. Our analysis highlighted the highly dynamic nature of STEC O157:H7 Stx-encoding bacteriophages and revealed the evolutionary history of a highly pathogenic clone emerging within sublineage IIb, a sublineage not previously associated with severe clinical symptoms.