mRNA control networks depend on recognition of specific RNA sequences. Pumilio-fem-3 mRNA binding factor (PUF) RNA-binding proteins achieve that specificity through variations on a conserved scaffold. Saccharomyces cerevisiae Puf3p achieves specificity through an additional binding pocket for a cytosine base upstream of the core RNA recognition site. Here we demonstrate that this chemically simple adaptation is prevalent and contributes to the diversity of RNA specificities among PUF proteins. Bioinformatics analysis shows that mRNAs associated with Caenorhabditis elegans fem-3 mRNA binding factor (FBF)-2 in vivo contain an upstream cytosine required for biological regulation. Crystal structures of FBF-2 and C. elegans PUF-6 reveal binding pockets structurally similar to that of Puf3p, whereas sequence alignments predict a pocket in PUF-11. For Puf3p, FBF-2, PUF-6, and PUF-11, the upstream pockets and a cytosine are required for maximal binding to RNA, but the quantitative impact on binding affinity varies. Furthermore, the position of the upstream cytosine relative to the core PUF recognition site can differ, which in the case of FBF-2 originally masked the identification of this consensus sequence feature. Importantly, other PUF proteins lack the pocket and so do not discriminate upstream bases. A structure-based alignment reveals that these proteins lack key residues that would contact the cytosine, and in some instances, they also present amino acid side chains that interfere with binding. Loss of the pocket requires only substitution of one serine, as appears to have occurred during the evolution of certain fungal species.