Microbial metalloenzymes constitute a large library of biocatalysts, a number of which have already been shown to catalyze the breakdown of toxic chemicals or industrially relevant chemical transformations. However, while there is considerable interest in harnessing these catalysts for biotechnology, for many of the enzymes, their large-scale production in active, soluble form in recombinant systems is a significant barrier to their use. In this work, we demonstrate that as few as three mutations can result in a 300-fold increase in the expression of soluble TrzN, an enzyme from Arthrobacter aurescens with environmental applications that catalyzes the hydrolysis of triazine herbicides, in Escherichia coli. Using a combination of X-ray crystallography, kinetic analysis, and computational simulation, we show that the majority of the improvement in expression is due to stabilization of the apoenzyme rather than the metal ion-bound holoenzyme. This provides a structural and mechanistic explanation for the observation that many compensatory mutations can increase levels of soluble-protein production without increasing the stability of the final, active form of the enzyme. This study provides a molecular understanding of the importance of the stability of metal ion free states to the accumulation of soluble protein and shows that differences between apoenzyme and holoenzyme structures can result in mutations affecting the stability of either state differently.