With early life likely to have existed in a hot environment, enzymes had to cope with an inherent drop in catalytic speed caused by lowered temperature. Here we characterize the molecular mechanisms underlying thermoadaptation of enzyme catalysis in adenylate kinase using ancestral sequence reconstruction spanning 3 billion years of evolution. We show that evolution solved the enzyme's key kinetic obstacle-how to maintain catalytic speed on a cooler Earth-by exploiting transition-state heat capacity. Tracing the evolution of enzyme activity and stability from the hot-start toward modern hyperthermophilic, mesophilic, and psychrophilic organisms illustrates active pressure versus passive drift in evolution on a molecular level, refutes the debated activity/stability trade-off, and suggests that the catalytic speed of adenylate kinase is an evolutionary driver for organismal fitness.