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 Å 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.