Actin-based motility is central to the pathogenicity of the intracellular bacterial pathogen Shigella. Two Shigella outer membrane proteins, IcsA and IcsP, are required for efficient actin-based motility in the host cell cytoplasm, and the genes encoding both proteins are carried on the large virulence plasmid. IcsA triggers actin polymerization on the surface of the bacterium, leading to the formation of an actin tail that allows both intra- and intercellular spread. IcsP, an outer membrane protease, modulates the amount and distribution of the IcsA protein on the bacterial surface through proteolytic cleavage of IcsA. Transcription of icsP is increased in the presence of VirB, a DNA-binding protein that positively regulates many genes carried on the large virulence plasmid. In Shigella dysenteriae, the small regulatory RNA RyhB, which is a member of the iron-responsive Fur regulon, suppresses several virulence-associated phenotypes by downregulating levels of virB in response to iron limitation. Here we show that the Fur/RyhB regulatory pathway downregulates IcsP levels in response to low iron concentrations in Shigella flexneri and that this occurs at the level of transcription through the RyhB-dependent regulation of VirB. These observations demonstrate that in Shigella species the Fur/RyhB regulatory pathway provides a mechanism to finely tune the expression of icsP in response to the low concentrations of free iron predicted to be encountered within colonic epithelial cells.