Pumilio is an RNA-binding protein that represses a network of mRNAs to control embryogenesis, stem cell fate, fertility and neurological functions in Drosophila. We sought to identify the mechanism of Pumilio-mediated repression and find that it accelerates degradation of target mRNAs, mediated by three N-terminal Repression Domains (RDs), which are unique to Pumilio orthologs. We show that the repressive activities of the Pumilio RDs depend on specific subunits of the Ccr4-Not (CNOT) deadenylase complex. Depletion of Pop2, Not1, Not2, or Not3 subunits alleviates Pumilio RD-mediated repression of protein expression and mRNA decay, whereas depletion of other CNOT components had little or no effect. Moreover, the catalytic activity of Pop2 deadenylase is important for Pumilio RD activity. Further, we show that the Pumilio RDs directly bind to the CNOT complex. We also report that the decapping enzyme, Dcp2, participates in repression by the N-terminus of Pumilio. These results support a model wherein Pumilio utilizes CNOT deadenylase and decapping complexes to accelerate destruction of target mRNAs. Because the N-terminal RDs are conserved in mammalian Pumilio orthologs, the results of this work broadly enhance our understanding of Pumilio function and roles in diseases including cancer, neurodegeneration and epilepsy.