The CCR4-NOT complex plays a crucial role in post-transcriptional mRNA regulation in eukaryotes. This complex catalyzes the removal of mRNA poly(A) tails, thereby repressing translation and committing an mRNA to degradation. The conserved core of the complex is assembled by the interaction of at least two modules: the NOT module, which minimally consists of NOT1, NOT2 and NOT3, and a catalytic module comprising two deadenylases, CCR4 and POP2/CAF1. Additional complex subunits include CAF40 and two newly identified human subunits, NOT10 and C2orf29. The role of the NOT10 and C2orf29 subunits and how they are integrated into the complex are unknown. Here, we show that the Drosophila melanogaster NOT10 and C2orf29 orthologs form a complex that interacts with the N-terminal domain of NOT1 through C2orf29. These interactions are conserved in human cells, indicating that NOT10 and C2orf29 define a conserved module of the CCR4-NOT complex. We further investigated the assembly of the D. melanogaster CCR4-NOT complex, and demonstrate that the conserved armadillo repeat domain of CAF40 interacts with a region of NOT1, comprising a domain of unknown function, DUF3819. Using tethering assays, we show that each subunit of the CCR4-NOT complex causes translational repression of an unadenylated mRNA reporter and deadenylation and degradation of a polyadenylated reporter. Therefore, the recruitment of a single subunit of the complex to an mRNA target induces the assembly of the complete CCR4-NOT complex, resulting in a similar regulatory outcome.