Enterohemorrhagic Escherichia coli (EHEC) (O157 and other serotypes) are zoonotic pathogens linked with severe human illnesses. The main virulence factors of EHEC are the Shiga toxins, among others. Most of the genes coding for these toxins are bacteriophage-encoded. Although ruminants are recognized as their main natural reservoir, water has also been documented as a way of transmission of EHEC. E. coli O157:H7 and other EHEC may contaminate waters (recreational, drinking or irrigation waters) through feces from humans and other animals. Indeed, the occurrence of EHEC carrying the stx2 gene in raw municipal sewage and animal wastewater from several origins has been widely documented. However, the evaluation of the persistence of naturally occurring EHEC in the environment is still difficult due to methodological problems. Methods proposed for the detection and isolation of stx-encoding bacteria, ranging from the classic culture-based methods to molecular approaches, and their application in the environment, are discussed here. Most virulence factors associated with these strains are linked to either plasmids or phages, and consequently they are likely to be subject to horizontal gene transfer between species or serotypes. Moreover, the presence of infectious stx-phages isolated as free particles in the environment and their high persistence in water systems suggest that they may contribute to the spread of stx genes, as they are directly involved in the emergence of new pathogenic strains, which might have important health consequences.