How the gut microflora influences the progression of bacterial infections is only beginning to be understood. Antibiotics are counterindicated for E. coli O157:H7 infections, limiting treatment options. An increased understanding of how the gut microflora directs O157:H7 virulence gene expression may lead to additional treatment options. This work identified E. coli strains that enhance the production of Shiga toxin by O157:H7 through the secretion of a proposed microcin. Microcins are natural antimicrobial peptides that target specific species, can act as alternatives to antibiotics, and mediate microbial competition. This work demonstrates another mechanism by which non-O157 E. coli strains may increase Shiga toxin production and adds to our understanding of microcins, a group of antimicrobials less well understood than colicins.