Random point mutagenesis does not access a large fraction of protein sequence space corresponding to primarily nonconservative amino acid substitutions. The cost of this limitation during directed evolution is unknown. Random point mutagenesis over the entire gene encoding the psychrophilic protease subtilisin S41 identified a pair of residues (Lys211 and Arg212) where mutations provided significant increases in thermostability. These were subjected to saturation mutagenesis to test whether the amino acids not easily accessible by point mutagenesis provide even better ``solutions'' to the thermostabilization challenge. A significant fraction of these variants surpassed the stability of the variants with point mutations. DNA sequencing revealed highly hydrophobic residues in the four most stable variants (Pro/Ala, Pro/Val, Leu/Val, and Trp/Ser). These nonconservative replacements, accessible only by multiple (two to three) base substitutions in a single codon, would be extremely rare in a point mutation library. Such replacements are also extremely rare in natural evolution. Saturation mutagenesis may be used advantageously during directed evolution to explore nonnatural evolution pathways and enable rapid improvement in protein traits.