Ccr4-Not is a conserved protein complex that shortens the 3′ poly(A) tails of eukaryotic mRNAs to regulate transcript stability and translation into proteins. RNA-binding proteins are thought to facilitate recruitment of Ccr4-Not to certain mRNAs, but lack of an in-vitro-reconstituted system has slowed progress in understanding the mechanistic details of this specificity. Here, we generate a fully recombinant Ccr4-Not complex that removes poly(A) tails from RNA substrates. The intact complex is more active than the exonucleases alone and has an intrinsic preference for certain RNAs. The RNA-binding protein Mmi1 is highly abundant in preparations of native Ccr4-Not. We demonstrate a high-affinity interaction between recombinant Ccr4-Not and Mmi1. Using in vitro assays, we show that Mmi1 accelerates deadenylation of target RNAs. Together, our results support a model whereby both RNA-binding proteins and the sequence context of mRNAs influence deadenylation rate to regulate gene expression.