Natural ribozymes and riboswitches are relatively rare in biology compared to their protein competitors. Only 14 distinct classes of ribozymes have been reported, and there are only ~45 classes of experimentally validated riboswitches known. However, it is likely that many more classes of structured noncoding RNAs with these functions remain hidden in the genomes of modern organisms. The validated classes of ribozymes and riboswitches provide evidence that they might have first existed during a period in evolution before the emergence of proteins. If true, then each new discovery possibly provides an opportunity to look back in time to an era when RNAs catalyzed chemical reactions and regulated biological systems. We have developed and further optimized a computational search pipeline that can reveal the presence of essentially every representative of a structured noncoding RNA from an entire bacterial genome. This approach makes practical the comprehensive analysis of the genomes from 100s of species. To date, we have completed the analysis of over 40 genomes, and have discovered at least 20 distinct classes of riboswitch candidates. One of these newly-found RNA classes has proven to regulate the expression of genes involved in the biosynthesis of the coenzyme thiamin. More importantly, the current pace of riboswitch discovery is consistent with our prediction that thousands of natural riboswitch classes remain to be discovered. Similarly, additional ribozyme classes are also likely to be revealed by this search strategy, which might expand the number of biochemical reactions catalyzed by RNA. Such discovery efforts should reveal numerous new roles for ribozymes, riboswitches and other bacterial noncoding RNAs.