In flies, Centrosomin (Cnn) forms a phosphorylation-dependent scaffold that recruits proteins to the mitotic centrosome, but how Cnn assembles into a scaffold is unclear. We show that scaffold assembly requires conserved leucine zipper (LZ) and Cnn-motif 2 (CM2) domains that co-assemble into a 2:2 complex in vitro. We solve the crystal structure of the LZ:CM2 complex, revealing that both proteins form helical dimers that assemble into an unusual tetramer. A slightly longer version of the LZ can form micron-scale structures with CM2, whose assembly is stimulated by Plk1 phosphorylation in vitro. Mutating individual residues that perturb LZ:CM2 tetramer assembly perturbs the formation of these micron-scale assemblies in vitro and Cnn-scaffold assembly in vivo. Thus, Cnn molecules have an intrinsic ability to form large, LZ:CM2-interaction-dependent assemblies that are critical for mitotic centrosome assembly. These studies provide the first atomic insight into a molecular interaction required for mitotic centrosome assembly. Display omitted •The conserved PReM and CM2 domains of Cnn co-assemble into micron-scale structures•The crystal structure of the PReM-LZ:CM2 complex is solved to 1.82 Å•Mutations that block PReM-LZ:CM2 assembly in vitro block centrosome assembly in vivo•Phosphorylation of PReM by Polo/Plk1 promotes scaffold assembly in vitro and in vivo Structural and biochemical analyses paint a new picture of how the pericentriolar material forms micron-scale structures that recruit PCM and nucleate microtubules.