Bacterial nucleoid-associated proteins H-NS and Hha modulate gene expression in response to environmental factors. The N-terminal domain of H-NS is involved in homomeric and heteromeric protein-protein interactions. Homomeric interaction leads to the formation of dimers and higher oligomers. Heteromeric interactions with Hha-like proteins modify the modulatory properties of H-NS. In this study, we have used NMR and mutagenesis of the N-terminal domain of H-NS to identify the Hha-binding region around helices H1 and H2 of H-NS. Two conserved arginine residues, R12 and R15, located in the same side and in adjacent turns of helix H2 are shown to be involved in two different protein-protein interactions: R12 is essential for Hha binding and does not affect H-NS dimer formation, and R15 does not affect Hha binding but is essential for the proper folding of H-NS dimers. Our results demonstrate a close structural connection between Hha-H-NS interactions and H-NS dimerization that may be involved in a possible mechanism for the modulation of the H-NS regulatory activity by Hha.