Variation in gene sequences generated by directed evolution approaches often does not assure a minimalist design for obtaining a desired property in proteins. While screening for enhanced thermostability, structural information was utilized in selecting mutations that are generated by error-prone PCR. By this approach we have increased the half-life of denaturation by 300-fold compared to the wild-type Bacillus subtilis lipase through three point mutations generated by only two cycles of error-prone PCR. At lower temperatures the activity parameters of the thermostable mutants are unaltered. High-resolution crystal structures of the mutants show subtle changes, which include stacking of tyrosine residues, peptide plane flipping and a better anchoring of the terminus, that challenge rational design and explain the structural basis for enhanced thermostability. The approach may offer an efficient and minimalist solution for the enhancement of a desired property of a protein.