RNA aptamers binding to C5 protein, the protein component of Escherichia coli RNase P, were selected and characterized as an initial step in elucidating the mechanism of action of C5 protein as an RNA-binding protein. Sequence analyses of the RNA aptamers suggest that C5 protein binds various RNA molecules with dissociation constants comparable to that of M1 RNA, the RNA component of RNase P. The dominant sequence, W2, was chosen for further study. Interactions between W2 and C5 protein were independent of Mg2+, in contrast to the Mg2+ dependency of M1 RNA-C5 protein interactions. The affinity of W2 for C5 protein increased with increasing concentration of monovalent NH4+, suggesting interactions via hydrophobic attraction. W2 forms a fairly stable complex with C5 protein, although the stability of this complex is lower than that of the complex of M1 RNA with C5 protein. The core RNA motif essential for interaction with C5 protein was identified as a stem-loop structure, comprising a 5 bp stem and a 20 nt loop. Our results strongly imply that C5 protein is an interacting partner protein of some cellular RNA species apart from M1 RNA.