A single regulatory protein can control the fate of many mRNAs with related functions. The Puf3 protein of Saccharomyces cerevisiae is exemplary, as it binds and regulates more than 100 mRNAs that encode proteins with mitochondrial function. Here we elucidate the structural basis of that specificity. To do so, we explore the crystal structures of Puf3p complexes with 2 cognate RNAs. The key determinant of Puf3p specificity is an unusual interaction between a distinctive pocket of the protein with an RNA base outside the "core" PUF-binding site. That interaction dramatically affects binding affinity in vitro and is required for regulation in vivo. The Puf3p structures, combined with those of Puf4p in the same organism, illuminate the structural basis of natural PUF-RNA networks. Yeast Puf3p binds its own RNAs because they possess a -2C and is excluded from those of Puf4p which contain an additional nucleotide in the core-binding site.