The shortening of the poly(A) tail of cytoplasmic mRNA (deadenylation) is a pivotal step in the regulation of gene expression in eukaryotic cells. Deadenylation impacts on both regulated mRNA decay as well as the rate of mRNA translation. An important enzyme complex involved in poly(A) shortening is the Ccr4-Not deadenylase. In addition to at least six non-catalytic subunits, it contains two distinct subunits with ribonuclease activity: a Caf1 subunit, characterized by a DEDD (Asp-Glu-Asp-Asp) domain, and a Ccr4 component containing an endonuclease-exonuclease-phosphatase (EEP) domain. In vertebrate cells, the complexity of the complex is further increased by the presence of paralogs of the Caf1 subunit (encoded by either CNOT7 or CNOT8) and the occurrence of two Ccr4 paralogs (encoded by CNOT6 or CNOT6L). In plants, there are also multiple Caf1 and Ccr4 paralogs. Thus, the composition of the Ccr4-Not complex is heterogeneous. The potential differences in the intrinsic enzymatic activities of the paralogs will be discussed. In addition, the potential redundancy, cooperation, and/or the extent of unique roles for the deadenylase subunits of the Ccr4-Not complex will be reviewed. Finally, novel approaches to study the catalytic roles of the Caf1 and Ccr4 subunits will be discussed.