We have solved the X-ray crystal structure of the RNA chaperone protein Hfq from the alpha-proteobacterium Caulobacter crescentus to 2.15-Å resolution, resolving the conserved core of the protein and the entire C-terminal domain (CTD). The structure reveals that the CTD of neighboring hexamers pack in crystal contacts, and that the acidic residues at the C-terminal tip of the protein interact with positive residues on the rim of Hfq, as has been recently proposed for a mechanism of modulating RNA binding. De novo computational models predict a similar docking of the acidic tip residues against the core of Hfq. We also show that C. crescentus Hfq has sRNA binding and RNA annealing activities and is capable of facilitating the annealing of certain Escherichia coli sRNA:mRNA pairs in vivo. Finally, we describe how the Hfq CTD and its acidic tip residues provide a mechanism to modulate annealing activity and substrate specificity in various bacteria.