The CCR4-NOT deadenylase complex is a master regulator of translation and mRNA stability. Its NOT module orchestrates recruitment of the catalytic subunits to target mRNAs. We report the crystal structure of the human NOT module formed by the CNOT1, CNOT2 and CNOT3 C-terminal (-C) regions. CNOT1-C provides a rigid scaffold consisting of two perpendicular stacks of HEAT-like repeats. CNOT2-C and CNOT3-C heterodimerize through their SH3-like NOT-box domains. The heterodimer is stabilized and tightly anchored to the surface of CNOT1 through an unexpected intertwined arrangement of peptide regions lacking defined secondary structure. These assembly peptides mold onto their respective binding surfaces and form extensive interfaces. Mutagenesis of individual interfaces and perturbation of endogenous protein ratios cause defects in complex assembly and mRNA decay. Our studies provide a structural framework for understanding the recruitment of the CCR4-NOT complex to mRNA targets.