Natural nucleic acids frequently rely on proteins for stabilization or catalytic activity. In contrast, nucleic acids selected in vitro can catalyze a wide range of reactions even in the absence of proteins. To augment selected nucleic acids with protein functionalities, we have developed a technique for the selection of protein-dependent ribozyme ligases. After randomizing a previously selected ribozyme ligase, L1, we selected variants that required one of two protein cofactors, a tyrosyl transfer RNA (tRNA) synthetase (Cyt18) or hen egg white lysozyme. The resulting nucleoprotein enzymes were activated several thousand fold by their cognate protein effectors, and could specifically recognize the structures of the native proteins. Protein-dependent ribozymes can potentially be adapted to novel assays for detecting target proteins, and the selection method's generality may allow the high-throughput identification of ribozymes capable of recognizing a sizable fraction of a proteome.