Escherichia coli RNase P is a ribonucleoprotein composed of M1 RNA and C5 protein. Previously, analysis of RNA aptamers selected for C5 protein from a synthetic RNA library showed that C5 protein could bind various RNA molecules as an RNA binding protein. In this study, we searched cellular RNA motifs that could be recognized by C5 protein by a genomic SELEX approach. We found various C5 protein-binding RNA motifs derived from E. coli genomic sequences. Our results suggest that C5 protein interacts with various cellular RNA species in addition to M1 RNA.