The Ccr4-Not complex is involved in several aspects of gene expression, including mRNA decay, translational repression and transcription. We determined the 2.8-Å-resolution crystal structure of a 120-kDa core complex of the Saccharomyces cerevisiae Not module comprising the C-terminal arm of Not1, Not2 and Not5. Not1 is a HEAT-repeat scaffold. Not2 and Not5 have extended regions that wrap around Not1 and around their globular domains, the Not boxes. The Not boxes resemble Sm folds and interact with each other with a noncanonical dimerization surface. Disruption of the interactions within the ternary complex has severe effects on growth in vivo. The ternary complex forms a composite surface that binds poly(U) RNA in vitro, with a site at the Not5 Not box. The results suggest that the Not module forms a versatile platform for macromolecular interactions.