Several enzymes are known to have evolved from non-catalytic proteins such as solute-binding proteins. Although attention has been focused on how binding sites evolve to become catalytic, an equally important question is: how do the structural dynamics of a binding protein change as it becomes an efficient enzyme? We have used ancestral sequence reconstruction to reconstruct evolutionary intermediates that link an ancestral amino-acid binding protein and a contemporary enzyme, cyclohexadienyl dehydratase. Using a combination of activity assays, X-ray crystallography and molecular dynamics (MD) simulations, we show that the new activity arose via distinct steps, including the functionalisation of the active site, optimisation of enzyme-substrate complementarity and changes to conformational sampling. Importantly, MD simulations and double electron-electron resonance measurements on proteins tagged with propargyl-DO3A-Gd(III) confirm that sampling of the unproductive open states (observed in the primitive dehydratases) are frozen out of the conformational landscape via remote mutations, eventually leading to an extract enzyme that exclusively samples only catalytically relevant, compact states.