Protein thermostability is a crucial factor for biotechnological enzyme applications. Protein engineering studies aimed at improving thermostability have successfully applied both directed evolution and rational design. However, for rational approaches, the major challenge remains the prediction of mutation sites and optimal amino acid substitutions. Recently, we showed that such mutation sites can be identified as structural weak spots by rigidity theory-based thermal unfolding simulations of proteins. Here, we describe and validate a unique, ensemble-based, yet highly efficient strategy to predict optimal amino acid substitutions at structural weak spots for improving a protein's thermostability. For this, we exploit the fact that in the majority of cases an increased structural rigidity of the folded state has been found as the cause for thermostability. When applied prospectively to lipase A from Bacillus subtilis, we achieved both a high success rate (25% over all experimentally tested mutations, which raises to 60% if small-to-large residue mutations and mutations in the active site are excluded) in predicting significantly thermostabilized lipase variants and a remarkably large increase in those variants' thermostability (up to 6.6°C) based on single amino acid mutations. When considering negative controls in addition and evaluating the performance of our approach as a binary classifier, the accuracy is 63% and increases to 83% if small-to-large residue mutations and mutations in the active site are excluded. The gain in precision (predictive value for increased thermostability) over random classification is 1.6-fold (2.4-fold). Furthermore, an increase in thermostability predicted by our approach significantly points to increased experimental thermostability (p < 0.05). These results suggest that our strategy is a valuable complement to existing methods for rational protein design aimed at improving thermostability.