In eukaryotes, shortening of the 3'-poly(A) tail is the rate-limiting step in the degradation of most mRNAs, and two major mRNA deadenylase complexes--Caf1-Ccr4 and Pan2-Pan3--play central roles in this process, referred to as deadenylation. However, the molecular mechanism triggering deadenylation remains elusive. Previously, we demonstrated that eukaryotic releasing factor eRF3 mediates deadenylation and decay of mRNA in a manner coupled to translation termination. Here, we report the mechanism of mRNA deadenylation. The eRF3-mediated deadenylation is catalyzed by both Caf1-Ccr4 and Pan2-Pan3. Interestingly, translation termination complexes eRF1-eRF3, Pan2-Pan3, and Caf1-Ccr4 competitively interact with polyadenylate-binding protein PABPC1. In each complex, eRF3, Pan3, and Tob, respectively, mediate PABPC1 binding, and a combination of a PAM2 motif and a PABC domain is commonly utilized for their contacts. A translation-dependent exchange of eRF1-eRF3 for the deadenylase occurs on PABPC1. Consequently, PABPC1 binding leads to the activation of Pan2-Pan3 and Caf1-Ccr4. From these results, we suggest a mechanism of mRNA deadenylation by Pan2-Pan3 and Caf1-Ccr4 in cooperation with eRF3 and PABPC1.