The nucleoid-associated proteins H-NS and StpA in Escherichia coli bind DNA as oligomers and are implicated in gene regulatory systems. There is evidence for both homomeric and heteromeric H-NS-StpA complexes. The two proteins show differential turnover, and StpA was previously found to be subject to protease-mediated degradation by the Lon protease. We investigated which regions of the H-NS protein are able to prevent degradation of StpA. A set of truncated H-NS derivatives was tested for their ability to mediate StpA stability and to form heteromers in vitro. The data indicate that H-NS interacts with StpA at two regions and that the presence of at least one of the H-NS regions is necessary for StpA stability. Our results also suggest that a proteolytically stable form of StpA, StpA(F21C), forms dimers, whereas wild-type StpA in the absence of H-NS predominantly forms tetramers or oligomers, which are more susceptible to proteolysis.