The H-NS family of proteins has been shown to participate in the regulation of a large number of genes in Gram-negative bacteria in response to environmental factors. In recent years, it has become apparent that proteins of the Hha family are essential elements for H-NS-regulated gene expression. Hha has been shown to bind H-NS, although the details for this interaction are still unknown. In the present paper, we report fluorescence anisotropy and NMR studies of the interaction between Hha and H-NS64, a truncated form of H-NS containing only its N-terminal dimerization domain. We demonstrate the initial formation of a complex between one Hha and two H-NS64 monomers in 150 mM NaCl. This complex seems to act as a nucleation unit for higher-molecular-mass complexes. NMR studies suggest that Hha is in equilibrium between two different conformations, one of which is stabilized by binding to H-NS64. A similar exchange is also observed for Hha in the absence of H-NS when temperature is increased to 37 degrees C, suggesting a key role for intrinsic conformational changes of Hha in modulating its interaction with H-NS.