The bacterial Sm-like protein Hfq is a central player in the control of bacterial gene expression. Hfq forms complexes with small regulatory RNAs (sRNAs) that use complementary "seed" sequences to target specific mRNAs. Hfq forms hexameric rings, which preferably bind uridine-rich RNA 3' ends on their proximal surface and adenine-rich sequences on their distal surface. However, many reported properties of Hfq/sRNA complexes could not be explained by these RNA binding modes. Here, we use the RybB sRNA to identify the lateral surface of Hfq as a third, independent RNA binding surface. A systematic mutational analysis and competition experiments demonstrate that the lateral sites have a preference for and are sufficient to bind the sRNA "body," including the seed sequence. Furthermore, we detect significant structural rearrangements of the Hfq/sRNA complex upon mRNA target recognition that lead to a release of the seed sequence, or of the entire sRNA molecule in case of an unfavorable 3' end. Consequently, we propose a molecular model for the Hfq/sRNA complex, where the sRNA 3' end is anchored in the proximal site of Hfq, whereas the sRNA body, including the seed sequence, is bound by up to six of the lateral sites. In contrast to previously proposed arrangements, the presented model explains how Hfq can protect large parts of the sRNA body while still allowing a rapid recycling of sRNAs. Furthermore, our model suggests molecular mechanisms for the function of Hfq as an RNA chaperone and for the molecular events that are initiated upon mRNA target recognition.