Enzymes find utility as therapeutics and for the production of specialty chemicals. Changing the amino acid sequence of an enzyme can increase solubility, but many such mutations disrupt catalytic activity. To evaluate this trade-off, we developed an experimental system to evaluate the relative solubility for nearly all possible single point mutants for two model enzymes. We find that the tendency for a given solubility-enhancing mutation to disrupt catalytic activity depends, among other factors, on how far the position is from the catalytic active site and whether that mutation has been sampled during evolution. We develop predictive models to identify mutations that enhance solubility without disrupting activity with an accuracy of 90%. These results have biotechnological applications.