Characterizing the adaptive landscapes that encompass the emergence of novel enzyme functions can provide molecular insights into both enzymatic and evolutionary mechanisms. Here, we combine ancestral protein reconstruction with biochemical, structural, and mutational analyses to characterize the functional evolution of methyl-parathion hydrolase (MPH), a xenobiotic organophosphate-degrading enzyme. We identify five mutations that are necessary and sufficient for the evolution of MPH from an ancestral dihydrocoumarin hydrolase. In-depth analyses of the adaptive landscapes encompassing this evolutionary transition revealed that a complex interaction network, defined in part by higher-order epistasis, determined the adaptive pathways that were available. By also characterizing the adaptive landscapes in terms of their functional activity towards three other OP substrates, we reveal that subtle differences in substrate substituents drastically alter the enzymes epistatic network by changing its intramolecular interactions. Our work suggests that the mutations function collectively to enable substrate recognition via subtle structural repositioning.