DsrA is an 87-nucleotide regulatory RNA of Escherichia coli that acts in trans by RNA-RNA interactions with two different mRNAs, hns and rpoS. DsrA has opposite effects on these transcriptional regulators. H-NS levels decrease, whereas RpoS (final sigma(s)) levels increase. Here we show that DsrA enhances hns mRNA turnover yet stabilizes rpoS mRNA, either directly or via effects on translation. Computational and RNA footprinting approaches led to a refined structure for DsrA, and a model in which DsrA interacts with the hns mRNA start and stop codon regions to form a coaxial stack. Analogous bipartite interactions exist in eukaryotes, albeit with different regulatory consequences. In contrast, DsrA base pairs in discrete fashion with the rpoS RNA translational operator. Thus, different structural configurations for DsrA lead to opposite regulatory consequences for target RNAs.