The conserved CCR4-NOT complex initiates the decay of mRNAs by catalyzing the shortening of their poly(A) tails in a process known as deadenylation. Recent studies have provided mechanistic insights into the action and regulation of this molecular machine. The two catalytic enzymatic subunits of the complex hydrolyze polyadenosine RNA. Notably, the non-catalytic subunits substantially enhance the complex's affinity and sequence selectivity for polyadenosine by directly contacting the RNA. An additional regulatory mechanism is the active recruitment of the CCR4-NOT to transcripts targeted for decay by RNA-binding proteins that recognize motifs or sequences residing predominantly in untranslated regions. This targeting and strict control of the mRNA deadenylation process emerges as a crucial nexus during post-transcriptional regulation of gene expression.