The Escherichia coli proteins H-NS is recognized as an important component among the major nucleoid-associated proteins. In studies of E. coli strains with defects in H-NS, we discovered a mutant that phenotypically restored stationary-phase viability (Rsv) of such strains. The Rsv phenotype was the result of a mutation that led to severalfold higher levels of the functionally and structurally related StpA protein. This mutation was a base pair change in the stpA structural gene, and the amino acid substitution in the StpA protein altered its turnover properties, suggesting a role for this residue in a cleavage site for proteolysis. We determined the stability of the StpA and the H-NS proteins and found that the StpA protein was degraded relatively rapidly in strains lacking functional H-NS, whereas H-NS remained stable irrespective of the presence/absence of StpA. Using protease-deficient mutants, we obtained evidence that the Lon protease was responsible for the degradation of StpA. The differential turnover of the nucleoid-associated proteins is suggested to contribute to the regulation of their stoichiometry and ratio in terms of homo- and heteromer formation. We conclude that StpA, in contrast to H-NS, is present mainly in heteromeric form in E. coli.