The eukaryotic Puf proteins regulate mRNA translation and degradation by binding the 3' untranslated regions of target mRNAs. Crystal structure analysis of a human Puf bound to RNA suggested a modular mode of binding, with specific amino acids within each of eight repeat domains contacting a single nucleotide of the target RNA. Here we study the mechanism by which the yeast Puf3p binds and stimulates the degradation of COX17 mRNA. Mutation of the predicted RNA-binding positions of Puf3p to those found in Puf5p demonstrated that a single amino acid change in Puf3p abolished detectable binding to COX17. Since this amino acid position in both Puf3p and Puf5p is predicted to contact an adenine in the respective target RNAs, the amino acid in Puf3p must play a more critical role in promoting COX17 interaction. In contrast, an amino acid change in the third repeat of Puf3p, which interacts with the only divergent nucleotide between the Puf3p and Puf5p targets, had no effect on binding COX17. These results argue that a simple set of rules cannot reliably link specific amino acid positions with target specificity. Each of these amino acid changes in Puf3p enhanced binding to the Puf5p target HO RNA, suggesting a different mode of binding to this target. Finally, we identified an outer surface loop that was dispensable for binding but was required to promote both rapid deadenylation and subsequent decapping of the COX17 mRNA, most likely as a point of protein-protein interactions.