New genes can arise by duplication and divergence, but there is a fundamental gap in our understanding of the relationship between these genes, the evolving proteins they encode, and the fitness of the organism. Here we used crystallography, NMR dynamics, kinetics, and mass spectrometry to explain the molecular innovations that arose during a previous real-time evolution experiment. In that experiment, the (βα)8 barrel enzyme HisA was under selection for two functions (HisA and TrpF), resulting in duplication and divergence of the hisA gene to encode TrpF specialists, HisA specialists, and bifunctional generalists. We found that selection affects enzyme structure and dynamics, and thus substrate preference, simultaneously and sequentially. Bifunctionality is associated with two distinct sets of loop conformations, each essential for one function. We observed two mechanisms for functional specialization: structural stabilization of each loop conformation and substrate-specific adaptation of the active site. Intracellular enzyme performance, calculated as the product of catalytic efficiency and relative expression level, was not linearly related to fitness. Instead, we observed thresholds for each activity above which further improvements in catalytic efficiency had little if any effect on growth rate. Overall, we have shown how beneficial substitutions selected during real-time evolution can lead to manifold changes in enzyme function and bacterial fitness. This work emphasizes the speed at which adaptive evolution can yield enzymes with sufficiently high activities such that they no longer limit the growth of their host organism, and confirms the (βα)8 barrel as an inherently evolvable protein scaffold. Significance New proteins can evolve by duplication of the genes that encode them, followed by specialization of the different copies. However, how the growth rate of an organism is coupled to the changes in a protein’s structure and function occurring during this process is not known. Here we show at atomic resolution how selection for the growth of a bacterium led to the evolution of HisA proteins with either a new function or two functions (old and new). We found that a distinct protein conformation is responsible for each function, and that a better enzyme leads to faster growth only up to a certain threshold. This study provides insight into how evolution works, from atomic to whole-organism levels.