Escherichia coli O104:H4 was associated with a severe foodborne disease outbreak originating in Germany in May 2011. More than 4000 illnesses and 50 deaths were reported. The outbreak strain was a typical enteroaggregative E. coli (EAEC) that acquired an antibiotic resistance plasmid and a Shiga-toxin 2 (Stx2)-encoding bacteriophage. Based on whole-genome phylogenies, the O104:H4 strain was most closely related to other EAEC strains; however, Stx2-bacteriophage are mobile, and do not necessarily share an evolutionary history with their bacterial host. In this study, we analyzed Stx2-bacteriophage from the E. coli O104:H4 outbreak isolates and compared them to all available Stx2-bacteriophage sequences. We also compared Stx2 production by an E. coli O104:H4 outbreak-associated isolate (ON-2011) to that of E. coli O157:H7 strains EDL933 and Sakai. Among the E. coli Stx2-phage sequences studied, that from O111:H- strain JB1-95 was most closely related phylogenetically to the Stx2-phage from the O104:H4 outbreak isolates. The phylogeny of most other Stx2-phage was largely concordant with their bacterial host genomes. Finally, O104:H4 strain ON-2011 produced less Stx2 than E. coli O157:H7 strains EDL933 and Sakai in culture; however, when mitomycin C was added, ON-2011 produced significantly more toxin than the E. coli O157:H7 strains. The Stx2-phage from the E. coli O104:H4 outbreak strain and the Stx2-phage from O111:H- strain JB1-95 likely share a common ancestor. Incongruence between the phylogenies of the Stx2-phage and their host genomes suggest the recent Stx2-phage acquisition by E. coli O104:H4. The increase in Stx2-production by ON-2011 following mitomycin C treatment may or may not be related to the high rates of hemolytic uremic syndrome associated with the German outbreak strain. Further studies are required to determine whether the elevated Stx2-production levels are due to bacteriophage or E. coli O104:H4 host related factors.