The bacterial Hfq protein modulates the stability or the translation of mRNAs and has recently been shown to interact with small regulatory RNAs in E. coli. Here we show that Hfq belongs to the large family of Sm and Sm-like proteins: it contains a conserved sequence motif, known as the Sm1 motif, forms a doughnut-shaped structure, and has RNA binding specificity very similar to the Sm proteins. Moreover, we provide evidence that Hfq strongly cooperates in intermolecular base pairing between the antisense regulator Spot 42 RNA and its target RNA. We speculate that Sm proteins in general cooperate in bimolecular RNA-RNA interaction and that protein-mediated complex formation permits small RNAs to interact with a broad range of target RNAs.