Atrazine chlorohydrolase (AtzA) and its close relative melamine deaminase (TriA) differ by just nine amino acid substitutions but have distinct catalytic activities. Together, they offer an informative model system to study the molecular processes that underpin the emergence of new enzymatic function. Here we have constructed the potential evolutionary trajectories between AtzA and TriA, and characterized the catalytic activities and biophysical properties of the intermediates along those trajectories. The order in which the nine amino acid substitutions that separate the enzymes could be introduced to either enzyme, while maintaining significant catalytic activity, was dictated by epistatic interactions, principally between three amino acids within the active site: namely, S331C, N328D and F84L. The mechanistic basis for the epistatic relationships is consistent with a model for the catalytic mechanisms in which protonation is required for hydrolysis of melamine, but not atrazine.