To sense and respond to their environment is a fundamental requirement for all organisms. This response often occurs through a carefully orchestrated regulation of genes. A major mode of gene-regulation in response to changing environments is via non-coding RNAs. This is especially evident in bacteria, where ligand-sensing riboswitches and RNA-protein complexes control important processes such as growth, metabolism, adaptations and responses to changing environments. We are interested in understanding how bacteria use RNAs to sense and respond to environmental cues. We have discovered that certain classes of bacteria utilize ethanolamine as a nutrient source; and this process is tightly regulated by a conserved dual stem RNA motif. We show that this dual stem RNA specifically recruits proteins containing the RNA-binding ANTAR domain. Ethanolamine induced phospho- cascades activate the ANTAR protein for RNA recognition. Remarkably, the structured dual stem RNA motif additionally interfaces with a coenzyme B12-sensing riboswitch; thus integrating substrate (ethanolamine) and cofactor (B12) sensing to control metabolism. Using a combination of RNA-protein biochemistry, biophysics and genetics we reveal the mechanism by which these small RNAs function. Using broad bioinformatic analyses, we show that the ANTAR protein-RNA regulatory network is widely prevalent across bacteria, suggesting that the central tenets for gene regulation by ANTAR may be conserved in nature. These findings open new avenues to address RNA-mediated mechanisms of signaling in pathogenic bacteria such as mycobacteria and pseudomonas where the biological roles of non-coding RNAs are poorly understood. In addition, we seek to understand how we can exploit regulatory RNA-protein networks to make useful genetic tools for biology.