A new cold-adapted protease subtilisin BPN' mutant, termed m-51, was successfully isolated by use of an evolutionary program consisting of two-step in vitro random mutagenesis, which we developed for the screening of mutant subtilisins with increased activity at low temperature. The m-51 mutant showed 70% higher catalytic efficiency, expressed by the k_cat/K_m value, than the wild-type at 10°C against N-succinyl-L-Ala-L-Ala-L-Pro-L-Phe-p-nitroanilide as a synthetic substrate. This cold-adaptation was achieved mainly by the increase in the k_cat value in a temperature-dependent manner. Genetic analysis revealed that m-51 had three mutations, Ala'Thr at position -31 (A-31T) in the prodomain, Ala→Val at position 88 (A88V), and Ala→Thr at position 98 (A98T). From kinetic parameters of the purified mutant enzymes, it was found that the A98T mutation led to 30% activity increase, which was enhanced up to 70% by the accompanying neutral mutation A88V. The A-31T mutation severely constrained the autoprocessing-mediated maturation of thee pro-subtilisin in the Escherichia coli expression system, thus probably causing an activity-non-detectable mutation in the first step of mutagenesis. No distinct change was observed in the thermal stability of any mutant or in the substrate specificity for m-51. In the molecular models of the two single mutants (A88V and A98T), relatively large displacements of alpha carbon atoms were found around the mutation points. In the model of the double mutant (A88V/A98T), on the other hand, the structural changes around the mutation point counterbalanced each other, and thus no crucial displacements occurred. This mutual effect may be related to the enhanced activity of the double mutant.