Foodborne Shiga toxin-producing Escherichia coli (STEC) cause severe diarrhea and hemolytic uremic syndrome (HUS) in humans. However, traditional methods for STEC sterilization are difficult to apply to fresh food. To control the pathogen, phage infecting E. coli O157:H7 were isolated and characterized. The isolated phage vB_EcoM-ECP26 had an icosahedral head and a contractile tail, and was classified as belonging to the Myoviridae family. The phage showed a broad host range against STEC and exhibited a large burst size of 1914 PFU/cell. The phage was highly stable at high temperatures (65 °C) and wide ranges of pH (4–10). The genome of vB_EcoM-ECP26 consists of 136,993 nucleotides, 214 open reading frames, and does not contain lysogenicity-related genes. Phylogenetic analysis showed that vB_EcoM-ECP26 is a V5-like species. STEC O157 growth was inhibited by vB_EcoM-ECP26 for 8 h. Furthermore, this phage not only significantly decreased the STEC population (p < 0.05), but also persisted in fresh lettuce at 4 °C for 5 days. Therefore, these results reveal that the novel lytic phage vB_EcoM-ECP26 could be a useful agent for the control of foodborne STEC.