Enteropathogenic Escherichia coli (EPEC) continues to be a leading cause of mortality and morbidity in children around the world. Two EPEC genomes have been fully sequenced: those of EPEC O127:H6 strain E2348/69 (United Kingdom, 1969) and EPEC O55:H7 strain CB9615 (Germany, 2003). The O55:H7 serotype is a recent precursor to the virulent enterohemorrhagic E. coli O157:H7. To explore the diversity of O55:H7 and better understand the clonal evolution of O157:H7, we fully sequenced EPEC O55:H7 strain RM12579 (California, 1974), which was collected 1 year before the first U.S. isolate of O157:H7 was identified in California. Phage-related sequences accounted for nearly all differences between the two O55:H7 strains. Additionally, O55:H7 and O157:H7 strains were tested for the presence and insertion sites of Shiga toxin gene (stx)-containing bacteriophages. Analysis of non-phage-associated genes supported core elements of previous O157:H7 stepwise evolutionary models, whereas phage composition and insertion analyses suggested a key refinement. Specifically, the placement and presence of lambda-like bacteriophages (including those containing stx) should not be considered stable evolutionary markers or be required in placing O55:H7 and O157:H7 strains within the stepwise evolutionary models. Additionally, we suggest that a 10.9-kb region (block 172) previously believed unique to O55:H7 strains can be used to identify early O157:H7 strains. Finally, we defined two subsets of O55:H7 strains that share an as-yet-unobserved or extinct common ancestor with O157:H7 strains. Exploration of O55:H7 diversity improved our understanding of the evolution of E. coli O157:H7 and suggested a key revision to accommodate existing and future configurations of stx-containing bacteriophages into current models.