PUF proteins are potent repressors that serve important roles in stem cell maintenance, neurological processes, and embryonic development. These functions are driven by PUF protein recognition of specific binding sites within the 3' untranslated regions of target mRNAs. In this study, we investigated mechanisms of repression by the founding PUF, Drosophila Pumilio, and its human orthologs. Here, we evaluated a previously proposed model wherein the Pumilio RNA binding domain (RBD) binds Argonaute, which in turn blocks the translational activity of the eukaryotic elongation factor 1A. Surprisingly, we found that Argonautes are not necessary for repression elicited by Drosophila and human PUFs in vivo. A second model proposed that the RBD of Pumilio represses by recruiting deadenylases to shorten the mRNA's polyadenosine tail. Indeed, the RBD binds to the Pop2 deadenylase and accelerates deadenylation; however, this activity is not crucial for regulation. Rather, we determined that the poly(A) is necessary for repression by the RBD. Our results reveal that poly(A)-dependent repression by the RBD requires the poly(A) binding protein, pAbp. Furthermore, we show that repression by the human PUM2 RBD requires the pAbp ortholog, PABPC1. Pumilio associates with pAbp but does not disrupt binding of pAbp to the mRNA. Taken together, our data support a model wherein the Pumilio RBD antagonizes the ability of pAbp to promote translation. Thus, the conserved function of the PUF RBD is to bind specific mRNAs, antagonize pAbp function, and promote deadenylation.