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), an 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 the mutations form a complex interaction network, defined in part by higher-order epistasis, that constrained the adaptive pathways available. By also characterizing the adaptive landscapes in terms of their functional activities towards three additional organophosphate substrates, we reveal that subtle differences in the polarity of the substrate substituents drastically alter the network of epistatic interactions. Our work suggests that the mutations function collectively to enable substrate recognition via subtle structural repositioning.