PUF proteins control gene expression by binding to the 3′- untranslated regions of specific mRNAs and triggering mRNA decay or translational repression. Here we focus on the mechanism of PUF-mediated regulation. The yeast PUF protein, Mpt5p, regulates HO mRNA and stimulates removal of its poly(A) tail (i.e. deadenylation). Mpt5p repression in vivo is dependent on POP2, a component of the cytoplasmic Ccr4p-Pop2p-Not complex that deadenylates mRNAs. In this study, we elucidate the individual roles of the Ccr4p and Pop2p deadenylases in Mpt5p-regulated deadenylation. Both in vivo and in vitro, Pop2p and Ccr4p proteins are required for Mpt5p-regulated deadenylation of HO. However, the requirements for the two proteins differ dramatically: the enzymatic activity of Ccr4p is essential, whereas that of Pop2p is dispensable. We conclude that Pop2p is a bridge through which the PUF protein recruits the Ccr4p enzyme to the target mRNA, thereby stimulating deadenylation. Our data suggest that PUF proteins may enhance mRNA degradation and repress expression by both deadenylation-dependent and -independent mechanisms, using the same Pop2p bridge to recruit a multifunctional Pop2p complex to the mRNA.