RNA-binding proteins (RBPs) play key roles in regulating virulence gene expression in pathogenic enterohaemorrhagic Escherichia coli (EHEC). To capture the RNA-binding proteome in EHEC, total RNA-associated protein purification (TRAPP) was employed and identified 443 RNA-associated proteins. These included 35 encoded within pathogenicity islands, with RNA-binding confirmed in vitro for four, including RhsFI. In vivo RNA targets for RhsFI included regulatory small RNAs (sRNAs) encoded in 3' UTRs. The rhsF-rhsFI locus encodes toxic effector and immunity proteins of the type 6 secretion system (T6SS). T6SS expression is repressed in EHEC, but internal transcription initiation generates a transcript encoding a truncated toxin (RhsFint) and downstream RhsFI. RhsFint has structural homology to nucleases and modelling predicted that RhsFint can dimerize with RhsFI, forming an extended RNA interaction face. Deletion of rhsFintrhsFI alters the expression of multiple operons in which embedded sRNAs are direct RhsFI targets. Loss of RhsFint-RhsFI significantly reduced adhesion to bovine cells in vitro, altered cell morphology and increased acid resistance. Our results indicate that the T6SS immunity protein, RhsFI, binds sRNAs in vivo and disrupts the sRNA regulatory network in EHEC to promote host colonization.