Post-transcriptional regulatory mechanisms are widely used to control gene expression programs of tissue development and physiology. Controlled 3' poly(A) tail-length changes of mRNAs provide a mechanistic basis of such regulation, affecting mRNA stability and translational competence. Deadenylases are a conserved class of enzymes that facilitate poly(A) tail removal, and their biochemical activities have been mainly studied in the context of single-cell systems. Little is known about the different deadenylases and their biological role in multicellular organisms. In this study, we identify and characterize all known deadenylases of Caenorhabditis elegans, and identify the germ line as tissue that depends strongly on deadenylase activity. Most deadenylases are required for hermaphrodite fertility, albeit to different degrees. Whereas ccr-4 and ccf-1 deadenylases promote germline function under physiological conditions, panl-2 and parn-1 deadenylases are only required under heat-stress conditions. We also show that the Ccr4-Not core complex in nematodes is composed of the two catalytic subunits CCR-4 and CCF-1 and the structural subunit NTL-1, which we find to regulate the stability of CCF-1. Using bulk poly(A) tail measurements with nucleotide resolution, we detect strong deadenylation defects of mRNAs at the global level only in the absence of ccr-4, ccf-1 and ntl-1, but not of panl-2, parn-1 and parn-2. Taken together, this study suggests that the Ccr4-Not complex is the main deadenylase complex in C. elegans germ cells. On the basis of this and as a result of evidence in flies, we propose that the conserved Ccr4-Not complex is an essential component in post-transcriptional regulatory networks promoting animal reproduction.