Many enzymes exhibit some catalytic promiscuity or substrate ambiguity. These weak activities do not affect the fitness of the organism under ordinary circumstances, but can serve as potential evolutionary precursors of new catalytic functions. We wondered whether different proteins with the same substrate ambiguous activity evolve differently under identical selection conditions. Patrick et al. (Patrick WM, Quandt EM, Swartzlander DB, Matsumura I. 2007. Multicopy suppression underpins metabolic evolvability. Mol Biol Evol. 24:2716–2722.) previously showed that three multicopy suppressors, gph, hisB, and ytjC, rescue ΔserB Escherichia coli cells from starvation on minimal media. We directed the evolution of variants of Gph, histidinol phosphatase (HisB), and YtjC that complemented ΔserB more efficiently, and characterized the effects of the amino acid changes, alone and in combination, upon the evolved phosphoserine phosphatase (PSP) activity. Gph and HisB are members of the HAD superfamily of hydrolases, but they adapted through different, kinetically distinguishable, biochemical mechanisms. All of the selected mutations, except N102T in YtjC, proved to be beneficial in isolation. They exhibited a pattern of antagonistic epistasis, as their effects in combination upon the kinetic parameters of the three proteins in reactions with phosphoserine were nonmultiplicative. The N102T mutation exhibited sign epistasis, as it was deleterious in isolation but beneficial in the context of other mutations. We also showed that the D57N mutation in the chromosomal copy of hisB is sufficient to suppress the ΔserB deletion. These results in combination show that proteomes can offer multiple mechanistic solutions to a molecular recognition problem.