Rational design and directed evolution have proved to be successful approaches to increase catalytic efficiencies of both natural and artificial enzymes. Protein dynamics is recognized as important, but due to the inherent flexibility of biological macromolecules it is often difficult to distinguish which conformational changes are directly related to function. Here, we use directed evolution on an impaired mutant of the proline isomerase CypA and identify two second-shell mutations that partially restore its catalytic activity. We show both kinetically, using NMR spectroscopy, and structurally, by room-temperature X-ray crystallography, how local perturbations propagate through a large allosteric network to facilitate conformational dynamics. The increased catalysis selected for in the evolutionary screen is correlated with an accelerated interconversion between the two catalytically essential conformational sub-states, which are both captured in the high-resolution X-ray ensembles. Our data provide a glimpse of an evolutionary trajectory and show how subtle changes can fine-tune enzyme function.