Heat-stable nucleoid structuring protein (H-NS) is an abundant prokaryotic protein that plays important roles in organizing chromosomal DNA and gene silencing. Two controversial binding modes were identified. H-NS binding stimulating DNA bridging has become the accepted mechanism, whereas H-NS binding causing DNA stiffening has been largely ignored. Here, we report that both modes exist, and that changes in divalent cations drive a switch between them. The stiffening form is present under physiological conditions, and directly responds to pH and temperature in vitro. Our findings have broad implications and require a reinterpretation of the mechanism by which H-NS regulates genes.