Most existing methods for improving protein activity are laborious and costly, as they either require knowledge of protein structure or involve expression and screening of a vast number of protein mutants. We describe here a successful first application of a novel approach, which requires no structural knowledge and is shown to significantly reduce the number of mutants that need to be screened. In the first phase of this study, around 7000 mutants were screened through standard directed evolution, yielding a 230-fold improvement in activity relative to the wild type. Using sequence analysis and site-directed mutagenesis, an additional single mutant was then produced, with 500-fold improved activity. In the second phase, a novel statistical method for protein improvement was used; building on data from the first phase, only 11 targeted additional mutants were produced through site-directed mutagenesis, and the best among them achieved a >1500-fold improvement in activity over the wild type. Thus, the statistical model underlying the experiment was validated, and its predictions were shown to reduce laboratory labor and resources.