Our long-term goal is to direct the evolution of novel protease variants. To this end we have engineered a new type of protease-activated reporter enzyme. Many protease-activated enzymes evolved in nature, but the introduction of novel regulatory mechanisms into normally unregulated enzymes poses a difficult design challenge. Random Elongation Mutagenesis  was used to fuse the p6 peptide, which is recognized and cleaved by HIV protease, and twelve random sequence amino acids to the C-termini of beta-glucuronidase (GUS) and alkaline phosphatase (AP). The resulting GUSp6-( NNN)12 and AP-p6-(NNN)12 libraries were expressed in E. coli and screened for clones that were inactivated by the C-terminal extension (tail). The inactivated clones were co-expressed with HIV protease, and those that were re-activated were isolated. The AP and GUS activities of the most responsive clones were each > 3.5-fold higher when co-expressed with HIV protease, and this activation is correlated with in vivo proteolysis. It should be possible to generalize this strategy to different reporter enzymes, different target proteases, and perhaps to other types of protein-modifying enzymes.