Exposure of E. coli to hydrogen peroxide induces the transcription of a small RNA denoted oxyS. The oxyS RNA is stable, abundant, and does not encode a protein. oxyS activates and represses the expression of numerous genes in E. coli, and eight targets, including genes encoding the transcriptional regulators FhlA and σ^s, were identified. oxyS expression also leads to a reduction in spontaneous and chemically-induced mutagenesis. Our results suggest that the oxyS RNA acts as a regulator that integrates adaptation to hydrogen peroxide with other cellular stress responses and helps to protect cells against oxidative damage.