The CCR4-NOT complex plays a crucial role in post-transcriptional mRNA regulation in eukaryotic cells. It catalyzes the removal of mRNA poly(A) tails, thereby repressing translation and committing mRNAs to decay. The conserved core of the complex consists of a catalytic module comprising two deadenylases (CAF1/POP2 and CCR4a/b) and the NOT module, which contains at least NOT1, NOT2 and NOT3. NOT1 bridges the interaction between the two modules and therefore, acts as a scaffold protein for the assembly of the complex. Here, we present the crystal structures of the CAF1-binding domain of human NOT1 alone and in complex with CAF1. The NOT1 domain comprises five helical hairpins that adopt an MIF4G (middle portion of eIF4G) fold. This NOT1 MIF4G domain binds CAF1 through a pre-formed interface and leaves the CAF1 catalytic site fully accessible to RNA substrates. The conservation of critical structural and interface residues suggests that the NOT1 MIF4G domain adopts a similar fold and interacts with CAF1 in a similar manner in all eukaryotes. Our findings shed light on the assembly of the CCR4-NOT complex and provide the basis for dissecting the role of the NOT module in mRNA deadenylation.