Introducing catalytic function into non-catalytic protein scaffolds remains a major challenge in the field of enzyme design. One explanation why designed enzymes are generally far less effective than their naturally occurring counterparts could be that computational enzyme design approaches often fail to consider the effect of conformational dynamics on enzyme activity. To investigate the role of conformational sampling in the emergence of new catalytic activity, we used ancestral protein reconstruction to characterise the evolutionary trajectory from a non-catalytic solute binding protein (SBP) to a catalytically active cyclohexadienyl dehydratase (CDT). Functional characterisation of extant homologs of CDT and reconstructed ancestral proteins revealed that CDT evolved from a cationic amino acid binding protein via several distinct steps. In addition to the introduction of a reactive catalytic motif within the active site and mutations that improved enzyme-substrate complementarity, remote substitutions were required to refine the structure of the active site and alter the conformational landscape of the enzyme. In particular, X-ray crystal structures and molecular dynamics revealed that substitutions along the evolutionary trajectory of CDT led to the reduction in the sampling of non-catalytic conformational states. This work highlights the importance of protein dynamics in the evolution of effective biological catalysts, and could help guide enzyme design efforts.