Introducing catalytic function into non-catalytic protein scaffolds remains a major challenge in the field of enzyme design. Using ancestral protein reconstruction, we investigated how nature navigates this problem by characterising 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 reveal that CDT evolved from an arginine-binding protein via an intermediate of unknown function. The mutations required to introduce CDT activity into a non-catalytic ancestral protein were identified using site-directed mutagenesis and directed evolution. Crystal structures and molecular dynamics simulations highlight the structural basis for the emergence of catalysis in the SBP fold and indicate that a change in the conformational landscape of the proteins is likely to have contributed to the evolution of CDT activity.