A hypothetical evolutionary pathway from a ribozyme to a catalytic RNA-protein complex (RNP) is proposed and examined. In this hypothesis for an early phase of molecular evolution, one RNA-RNA interaction in the starting ribozyme is replaced with an RNA-protein interaction via two intermediary stages. At each stage, the original RNA-RNA interaction and a newly introduced RNA-protein interaction are designed to coexist. The catalytic RNPs corresponding to the intermediary stages were constructed by employing the Tetrahymena ribozyme together with molecular modeling. Analyses of the RNPs indicate that the protein can fully replace the original role of the RNA-RNA interaction in the starting ribozyme and that the association of a protein with a ribozyme might be beneficial for improving the ribozymatic activity.