We unveil the intimate relationship between protein dynamics and allostery by following the trajectories of model proteins in their conformational and sequence spaces. Starting from a nonallosteric hyperthermophilic malate dehydrogenase, we have tracked the role of protein dynamics in the evolution of the allosteric capacity. Based on a large phylogenetic analysis of the malate (MalDH) and lactate dehydrogenase (LDH) superfamily, we identified two amino acid positions that could have had a major role for the emergence of allostery in LDHs, which we targeted for investigation by site-directed mutagenesis. Wild-type MalDH and the single and double mutants were tested with respect to their substrate recognition profiles. The double mutant displayed a sigmoid-shaped profile typical of homotropic activation in LDH. By using molecular dynamics simulations, we showed that the mutations induce a drastic change in the protein sampling of its conformational landscape, making transiently T-like (inactive) conformers, typical of allosteric LDHs, accessible. Our data fit well with the seminal key concept linking protein dynamics and evolvability. We showed that the selection of a new phenotype can be achieved by a few key dynamics-enhancing mutations causing the enrichment of low-populated conformational substates.