Small noncoding RNAs (sRNAs) regulate the response of bacteria to environmental stress in conjunction with the Sm-like RNA binding protein Hfq. DsrA sRNA stimulates translation of the RpoS stress response factor in Escherichia coli by base-pairing with the 5' leader of the rpoS mRNA and opening a stem-loop that represses translation initiation. We report that rpoS leader sequences upstream of this stem-loop greatly increase the sensitivity of rpoS mRNA to Hfq and DsrA. Native gel mobility shift assays show that Hfq increases the rate of DsrA binding to the full 576 nt rpoS leader as much as 50-fold. By contrast, base-pairing with a 138-nt RNA containing just the repressor stem-loop is accelerated only twofold. Deletion and mutagenesis experiments showed that sensitivity to Hfq requires an upstream AAYAA sequence. Leaders long enough to contain this sequence bind Hfq tightly and form stable ternary complexes with Hfq and DsrA. A model is proposed in which Hfq recruits DsrA to the rpoS mRNA by binding both RNAs, releasing the self-repressing structure in the mRNA. Once base-pairing between DsrA and rpoS mRNA is established, interactions between Hfq and the mRNA may stabilize the RNA complex by removing Hfq from the sRNA.