H-NS, a protein found in Gram-negative bacteria, is involved in structuring the bacterial chromosome and acts as a global regulator for the expression of a wide variety of genes. These functions are correlated with both its DNA-binding and oligomerization properties. We have identified the minimal dimerization domain of H-NS, a 46 amino acid-long N-terminal fragment, and determined its structure using heteronuclear NMR spectroscopy. The highly intertwined structure of the dimer, reminiscent of a handshake, defines a new structural fold, which may offer a possibility for discriminating prokaryotic from eukaryotic proteins in drug design. Using mutational analysis, we also show that this N-terminal domain actively contributes to DNA binding, conversely to the current paradigm. Together, our data allows us to propose a model for the action of full length H-NS.