Proteins bind and control mRNAs, directing their localization, translation, and stability. Members of the PUF family of RNA-binding proteins control multiple mRNAs in a single cell, and play key roles in development, stem cell maintenance and memory formation. Here we demonstrate the conservation of PUF regulatory networks by bioinformatic analysis. We identified the mRNA targets of two Saccharomyces cerevisiae PUF proteins, Puf3p and Puf5p, and two Neurospora crassa PUF proteins, PUF3 and PUF5, by UV-crosslinking-affinity purification and high-throughput sequencing (HITS-CLIP). Taken together these data allowed us to elucidate a rewiring of a nulcear-endcoded circuit of mitochondrial related mRNAs. S. cerevisiae Puf5p associates with ~1,000 RNAs, suggesting that it is a broad spectrum regulator. The binding sites recognized by both Puf5 proteins are diverse, with variable spacer lengths between two specific sequences. S. cerevisiae Puf3p binds a group of RNAs significantly enriched for nuclear encoded RNAs that code for mitochondrial proteins. Many of these orthologous RNAs are bound by N. crassa PUF5. This constitutes a switch, from Puf3p to Puf5, regulation, when comparing S. cerevisiae and N. crassa PUF regulatory networks. Crystal structures of S. cerevisiae Puf5p-RNA complexes reveal that the protein scaffold presents an exceptionally flat and extended interaction surface relative to other PUF proteins. A single PUF protein repeat is sufficient to induce broadening of specificity. Changes in protein architecture, such as alterations in curvature, may have led to evolution of mRNA regulatory networks which we observe.