Most large ribozymes require protein cofactors in order to function efficiently. The yeast mitochondrial bI3 group I intron requires two proteins for efficient splicing, Mrs1 and the bI3 maturase. Mrs1 has evolved from DNA junction resolvases to function as an RNA cofactor for at least two group I introns; however, the RNA binding site and the mechanism by which Mrs1 facilitates splicing were unknown. Here we use high-throughput RNA structure analysis to show that Mrs1 binds a ubiquitous RNA tertiary structure motif, the GNRA tetraloop-receptor interaction, at two sites in the bI3 RNA. Mrs1 also interacts at similar tetraloop-receptor elements, as well as other structures, in the self-folding Azoarcus group I intron and in the RNase P enzyme. Thus, Mrs1 recognizes general features found in the tetraloop-receptor motif. Identification of the two Mrs1 binding sites now makes it possible to create a model of the complete six-component bI3 ribonucleoprotein. All protein cofactors bind at the periphery of the RNA such that every long-range RNA tertiary interaction is stabilized by protein binding, involving either Mrs1 or the bI3 maturase. This work emphasizes the strong evolutionary pressure to bolster RNA tertiary structure with RNA-binding interactions as seen in the ribosome, spliceosome, and other large RNA machines.