The rpoS mRNA encodes a stress response transcription factor in Escherichia coli. It is one of a growing number of mRNAs found to be regulated by small RNAs (sRNA). Translation initiation of rpoS mRNA is enhanced by two sRNAs, DsrA and RprA, that pair to the same site near the rpoS start codon in the presence of the Hfq protein. In this work, we examine the interaction of E. coli Hfq with RprA and two portions of the rpoS mRNA leader region. One rpoS RNA, rpoS-L, contained the entire 565-nucleotide leader region, while the other, rpoS-S, contained the 199-nucleotide sequence surrounding the start codon. An RNase H assay indicated both rpoS RNAs have similar secondary structures in the translation initiation region. Hfq formed two complexes with RprA in a gel mobility assay with binding parameters similar to values previously determined for DsrA. Unlike DsrA, Hfq binding to RprA was inhibited by poly(A) and influenced by Hfq mutations on both the distal and proximal surfaces. Hfq increased the level of RprA binding to both rpoS RNAs but showed a much larger enhancement when rpoS-L, the entire leader region, was examined. The lower affinity of RprA for rpoS-L versus rpoS-S in the absence of Hfq suggests that Hfq overcomes an inhibitory structure within rpoS-L in stimulating RprA binding. Similar results were obtained with DsrA. The results indicate that the full upstream leader sequence of rpoS mRNA influences Hfq-facilitated annealing of RprA and DsrA and is likely to be involved in its regulation.