Small non-coding RNAs (sRNA) have emerged as important elements of gene regulatory circuits. In enterobacteria such as Escherichia coli and Salmonella many of these sRNAs interact with the Hfq protein, an RNA chaperone similar to mammalian Sm-like proteins and act in the post-transcriptional regulation of many genes. A number of these highly conserved ribo-regulators are stringently regulated at the level of transcription and are part of major regulons that deal with the immediate response to various stress conditions, indicating that every major transcription factor may control the expression of at least one sRNA regulator. Here, we extend this view by the identification and characterization of a highly conserved, anaerobically induced small sRNA in E. coli, whose expression is strictly dependent on the anaerobic transcriptional fumarate and nitrate reductase regulator (FNR). The sRNA, named FnrS, possesses signatures of base-pairing RNAs, and we show by employing global proteomic and transcriptomic profiling that the expression of multiple genes is negatively regulated by the sRNA. Intriguingly, many of these genes encode enzymes with “aerobic” functions or enzymes linked to oxidative stress. Furthermore, in previous work most of the potential target genes have been shown to be repressed by FNR through an undetermined mechanism. Collectively, our results provide insight into the mechanism by which FNR negatively regulates genes such as sodA, sodB, cydDC, and metE, thereby demonstrating that adaptation to anaerobic growth involves the action of a small regulatory RNA.