Bovine enterokinase light chain (EKL) is an industrially useful protease for accurate removal of affinity-purification tags from high-value biopharmaceuticals. However, recombinant expression in Escherichia coli produces insoluble inclusion bodies, requiring solubilisation, refolding, and autocatalytic activation to recover functional enzyme. Error-prone PCR and DNA shuffling of the EKL gene, T7 promotor, lac operon, ribosome binding site, and pelB leader sequence, yielded 321 unique variants after screening ~ 6500 colonies. The best variants had > 11,000-fold increased total activity in lysates, producing soluble enzyme that no longer needed refolding. Further characterisation identified the factors that improved total activity from an inactive and insoluble starting point. Stability was a major factor, whereby melting temperatures > 48.4°C enabled good expression at 37°C. Variants generally did not alter catalytic efficiency as measured by kcat/Km, which improved for only one variant. Codon optimisation improved the total activity in lysates produced at 37°C. However, non-optimised codons and expression at 30°C gave the highest activity through improved protein quality, with increased kcat and Tm values. The 321 variants were statistically analysed and mapped to protein structure. Mutations detrimental to total activity and stability clustered around the active site. By contrast, variants with increased total activity tended to combine stabilising mutations that did not disrupt the active site.