Bacterial small noncoding RNAs carry out both positive and negative regulation of gene expression by pairing with mRNAs; in Escherichia coli, this regulation often requires the RNA chaperone Hfq. Three small regulatory RNAs (sRNAs), DsrA, RprA, and ArcZ, positively regulate translation of the sigma factor RpoS, each pairing with the 5' leader to open up an inhibitory hairpin. In vitro, rpoS interaction with sRNAs depends upon an (AAN)(4) Hfq-binding site upstream of the pairing region. Here we show that both Hfq and this Hfq binding site are required for RprA or ArcZ to act in vivo and to form a stable complex with rpoS mRNA in vitro; both were partially dispensable for DsrA at 37 degrees C. ArcZ sRNA is processed from 121 nt to a stable 56 nt species that contains the pairing region; only the 56 nt ArcZ makes a strong Hfq-dependent complex with rpoS. For each of these sRNAs, the stability of the sRNA*mRNA complexes, rather than their rate of formation, best predicted in vivo activity. These studies demonstrate that binding of Hfq to the rpoS mRNA is critical for sRNA regulation under normal conditions, but if the stability of the sRNA*mRNA complex is sufficiently high, the requirement for Hfq can be bypassed.