Anteroposterior patterning of the Drosophila embryo depends on a gradient of Nanos protein arising from the posterior pole. This gradient results from both nanos mRNA translational repression in the bulk of the embryo and translational activation of nanos mRNA localized at the posterior pole. Two mechanisms of nanos translational repression have been described, at the initiation step and after this step. Here we identify a novel level of nanos translational control. We show that the Smaug protein bound to the nanos 3' UTR recruits the deadenylation complex CCR4-NOT, leading to rapid deadenylation and subsequent decay of nanos mRNA. Inhibition of deadenylation causes stabilization of nanos mRNA, ectopic synthesis of Nanos protein and head defects. Therefore, deadenylation is essential for both translational repression and decay of nanos mRNA. We further propose a mechanism for translational activation at the posterior pole. Translation of nanos mRNA at the posterior pole depends on oskar function. We show that Oskar prevents the rapid deadenylation of nanos mRNA by precluding its binding to Smaug, thus leading to its stabilization and translation. This study provides insights into molecular mechanisms of regulated deadenylation by specific proteins and demonstrates its importance in development.