Drosophila melanogaster Bag-of-marbles (Bam) promotes germline stem cell (GSC) differentiation by repressing the expression of mRNAs encoding stem cell maintenance factors. Bam interacts with Benign gonial cell neoplasm (Bgcn) and the CCR4 deadenylase, a catalytic subunit of the CCR4–NOT complex. Bam has been proposed to bind CCR4 and displace it from the CCR4–NOT complex. Here, we investigated the interaction of Bam with the CCR4–NOT complex by using purified recombinant proteins. Unexpectedly, we found that Bam does not interact with CCR4 directly but instead binds to the CAF40 subunit of the complex in a manner mediated by a conserved N-terminal CAF40-binding motif (CBM). The crystal structure of the Bam CBM bound to CAF40 reveals that the CBM peptide adopts an α-helical conformation after binding to the concave surface of the crescent-shaped CAF40 protein. We further show that Bam-mediated mRNA decay and translational repression depend entirely on Bam's interaction with CAF40. Thus, Bam regulates the expression of its mRNA targets by recruiting the CCR4–NOT complex through interaction with CAF40.