Hfq is a bacterial RNA binding protein that facilitates small RNA-mediated posttranscriptional gene regulation. In Vibrio cholerae, Hfq and four Hfq-dependent small RNAs are essential for the expression of virulence genes, but little is known about this mechanism at the molecular level. To better understand V. cholerae Hfq structure and mechanism, we characterized the protein, alongside Escherichia coli Hfq for comparison, using biochemical and biophysical techniques. The N-terminal domain (NTD) of the two proteins is highly conserved, but the C-terminal regions (CTRs) vary in both sequence and length. Small-angle X-ray scattering studies showed that both proteins adopt a star-shaped hexameric structure in which the conserved NTD adopts the expected Sm fold while the variable CTR is disordered and extends radially outwards from the folded core. Despite their structural similarity, SDS-PAGE stability assays and collision-induced dissociation mass spectrometry revealed that the V. cholerae hexamer is less stable than that of E. coli. We propose that this is due to minor differences between the intersubunit interface formed by the NTDs and the ability of the E. coli CTR to stabilize this interface. However, based on electrophoretic mobility shift assays, the divergent CTRs do appear to perform a common function with regard to RNA-binding specificity. Overall, the similarities and differences in the fundamental properties of V. cholerae and E. coli Hfq provide insight into their assembly and molecular mechanisms.