In bacteria, regulation in response to environmental cues is mediated by many mechanisms. These include a variety of specific interactions between complex tertiary structures formed by the mRNA and a variety of cellular signals. Despite their complexity, such RNA regulators appear to be rapidly evolving and are often not conserved across broad taxonomic groups. There are several documented instances where analogous biological functions are regulated by very distinct RNA regulators in diverse bacterial species. Our laboratory is utilizing the structured RNA cis-regulators that respond to ribosomal proteins as a model to explore the factors contributing the diversity of analogous RNA regulators observed. These regulators typically act by interacting with a protein to inhibit translation initiation and allow stoichiometric production of ribosome components. We have focused on ribosomal protein S15 and its interactions with four different mRNA structures that occur in diverse bacterial species. We find that the diversity of mRNA structures apparent across different bacteria phyla is partially driven by differences in the recognition surfaces of diverged S15 homologs. However, in vitro selection experiments have also demonstrated that such regulators are relatively frequent in sequence space. A population of RNAs selected to interact with a single S15 homolog is incredibly diverse. High-throughput sequencing revealed a population of >4 million distinct sequences with few easily recognizable motifs apparent. Furthermore, 50% of sequences tested not only interact with S15 in vitro, but also allow regulation of an Escherichia coli reporter in response to S15, in some cases with characteristics comparable to the native regulator. These experiments suggest that the diversity of RNA regulators observed in nature is a consequence of both co-evolution between diverging protein homologs and their corresponding RNA regulators, as well as the plasticity of RNA structure that allows many potential solutions to exist within sequence space.