The eukaryotic Ccr4/Caf1/Not complex is involved in deadenylation of mRNAs. The Caf1 and Ccr4 subunits both potentially have deadenylating enzyme activity. We investigate here the roles of Ccr4 and Caf1 in deadenylation in two organisms that separated early in eukaryotic evolution: humans and trypanosomes. In Trypanosoma brucei, we found a complex containing CAF1, NOT1, NOT2 and NOT5, DHH1 and a possible homologue of Caf130; no homologue of Ccr4 was found. Trypanosome CAF1 has deadenylation activity, and is essential for cell survival. Depletion of trypanosome CAF1 delayed deadenylation and degradation of constitutively expressed mRNAs. Human cells have two isozymes of Caf1: simultaneous depletion of both inhibited degradation of an unstable reporter mRNA. In both species, depletion of Caf1 homologues inhibited deadenylation of bulk RNA and resulted in an increase in average poly(A) tail length.