Controlled shortening of the poly(A) tail of mRNAs is the first step in eukaryotic mRNA decay and can also be used for translational inactivation of mRNAs. The CCR4-NOT complex is the most important among a small number of deadenylases, enzymes catalyzing poly(A) tail shortening. Rates of poly(A) shortening differ between mRNAs as the CCR4-NOT complex is recruited to specific mRNAs by means of either sequence-specific RNA binding proteins or miRNAs. This review summarizes our current knowledge concerning the subunit composition and deadenylation activity of the Drosophila CCR4-NOT complex and the mechanisms by which the complex is recruited to particular mRNAs. We discuss genetic data implicating the complex in the regulation of specific mRNAs, in particular in the context of development.