Enterohemorrhagic Escherichia coli (EHEC), an emerging food- and water-borne hazard, is highly pathogenic to humans. In the environment, EHEC must survive phosphate (Pi) limitation. The response to such Pi starvation is an induction of the Pho regulon including the Pst system that senses Pi variation. The interplay between the virulence of EHEC, Pho-Pst system and environmental Pi remains unknown. To understand the effects of Pi deprivation on the molecular mechanisms involved in EHEC survival and virulence under Pho regulon control, we undertook transcriptome profiling of the EDL933 wild-type strain grown under high Pi and low Pi conditions and its isogenic ΔphoB mutant grown in low Pi conditions. The differentially expressed genes included 1067 Pi-dependent genes and 603 PhoB-dependent genes. Of these 131 genes were both Pi and PhoB-dependent. Differentially expressed genes that were selected included those involved in Pi homeostasis, cellular metabolism, acid stress, oxidative stress and RpoS-dependent stress responses. Differentially expressed virulence systems included the locus of enterocyte effacement (LEE) encoding the type-3 secretion system (T3SS) and its effectors, as well as BP-933W prophage encoded Shiga toxin 2 genes. Moreover, PhoB directly regulated LEE and stx2 gene expression through binding to specific Pho boxes. However, in Pi-rich medium, constitutive activation of the Pho regulon decreased LEE gene expression and reduced adherence to HeLa cells. Together, these findings reveal that EHEC has evolved a sophisticated response to Pi limitation involving multiple biochemical strategies that contribute to its ability to respond to variations in environmental Pi and to coordinating the virulence response.