The histone-like nucleoid structuring (H-NS) protein plays a fundamental role in DNA condensation and is a key regulator of enterobacterial gene expression in response to changes in osmolarity, pH, and temperature. The protein is capable of high-order self-association via interactions of its oligomerization domain. Using crystallography, we have solved the structure of this complete domain in an oligomerized state. The observed superhelical structure establishes a mechanism for the self-association of H-NS via both an N-terminal antiparallel coiled-coil and a second, hitherto unidentified, helix-turn-helix dimerization interface at the C-terminal end of the oligomerization domain. The helical scaffold suggests the formation of a H-NS:plectonemic DNA nucleoprotein complex that is capable of explaining published biophysical and functional data, and establishes a unifying structural basis for coordinating the DNA packaging and transcription repression functions of H-NS.