One central goal in molecular evolution is to pinpoint the mechanisms and evolutionary forces that cause an enzyme to change its substrate specificity; however, these processes remain largely unexplored. Using the glycolytic ADP-dependent kinases of archaea, including the orders Thermococcales , Methanosarcinales , and Methanococcales , as a model and employing an approach involving paleoenzymology, evolutionary statistics, and protein structural analysis, we could track changes in substrate specificity during ADP-dependent kinase evolution along with the structural determinants of these changes. To do so, we studied five key resurrected ancestral enzymes as well as their extant counterparts. We found that a major shift in function from a bifunctional ancestor that could phosphorylate either glucose or fructose 6-phosphate (fructose-6-P) as a substrate to a fructose 6-P-specific enzyme was started by a single amino acid substitution resulting in negative selection with a ground-state mode against glucose and a subsequent 1,600-fold change in specificity of the ancestral protein. This change rendered the residual phosphorylation of glucose a promiscuous and physiologically irrelevant activity, highlighting how promiscuity may be an evolutionary vestige of ancestral enzyme activities, which have been eliminated over time. We also could reconstruct the evolutionary history of substrate utilization by using an evolutionary model of discrete binary characters, indicating that substrate uses can be discretely lost or acquired during enzyme evolution. These findings exemplify how negative selection and subtle enzyme changes can lead to major evolutionary shifts in function, which can subsequently generate important adaptive advantages, for example, in improving glycolytic efficiency in Thermococcales ., (© 2017 by The American Society for Biochemistry and Molecular Biology, Inc.)