In prokaryotes, Hfq regulates translation by modulating the structure of numerous RNA molecules by binding preferentially to A/U-rich sequences. To elucidate the mechanisms of target recognition and translation regulation by Hfq, we determined the crystal structures of the Staphylococcus aureus Hfq and an Hfq-RNA complex to 1.55 and 2.71 A resolution, respectively. The structures reveal that Hfq possesses the Sm-fold previously observed only in eukaryotes and archaea. However, unlike these heptameric Sm proteins, Hfq forms a homo-hexameric ring. The Hfq-RNA structure reveals that the single-stranded hepta-oligoribonucleotide binds in a circular conformation around a central basic cleft, whereby Tyr42 residues from adjacent subunits stack with six of the bases, and Gln8, outside the Sm motif, provides key protein-base contacts. Such binding suggests a mechanism for Hfq function.