In many bacteria, a homodimer of structural-maintenance-of-chromosomes proteins associates with two regulatory subunits (known as ScpA and ScpB), assembling a protein complex that plays a crucial role in chromosome organization and segregation. It remains poorly understood, however, how this complex might work at the mechanistic level. Here, we report crystal structures of the ScpAB core complex that display a highly unusual structure in which the central segment of ScpA winds around an asymmetrically oriented ScpB dimer. The two C-terminal domains of the ScpB dimer primarily interact with different regions of ScpA with different affinities. Moreover, flexible interdomain regions of ScpB contribute to a dynamic folding process of the ScpAB subcomplex. Together with other genetic and biochemical assays, we provide evidence that internal structural changes of the ScpAB subcomplex are tightly coupled with activation of the structural-maintenance-of-chromosomes ATPase.