In enteric bacteria, proteins of the Hha/YmoA family play a role in the regulation of gene expression in response to environmental factors. Interaction of both Hha and YmoA with H-NS has been reported, and an Hha/H-NS complex has been shown to modulate expression in Escherichia coli of the haemolysin operon of plasmid pHly152. In addition to the hns gene, the chromosome of E. coli and other enteric bacteria also includes the stpA gene that encodes the StpA protein, an H-NS paralogue. We report here the identification of the Hha paralogue in E. coli, the YdgT protein. As Hha paralogue, YdgT appears to fulfil some of the functions reported for StpA as H-NS paralogue: YdgT is overexpressed in hha mutants and can compensate, at least partially, some of the hha-induced phenotypes. We also demonstrate that YdgT interacts both with H-NS and with StpA. Protein cross-linking studies showed that YdgT/H-NS heteromeric complexes are generated within the bacterial cell. The StpA protein, which is subjected to Lon-mediated turnover, was less stable in the absence of Hha or YdgT. Our findings suggest that Hha, YdgT and StpA may form complexes in vivo.