The selection of novel proteins or enzymes from random protein libraries has come to be a major objective in current biology, and these enzymes should prove useful in various biological and biomedical fields. New technologies such as in vitro selection of proteins in cell-free systems have high potential to realize evolutionary molecular engineering of proteins. This review highlights an application of insertional mutagenesis of proteins to evolutionary molecular engineering. Random sequence proteins are inserted into the surface of a host enzyme which serves as a scaffold to display random protein libraries. Constraints on random polypeptide conformations owing to the proximity of N- and C-termini on the scaffold would result in greater screening efficiency of libraries. The scaffold enzyme is also used as a probe for monitoring the hill climbing of random sequence proteins on a fitness landscape and navigating rapid protein folding in the sequence space.