Protein evolution is crucial for organismal adaptation and fitness. This process takes place by shaping a given 3-dimensional fold for its particular biochemical function within the metabolic requirements and constraints of the environment. The complex interplay between sequence, structure, functionality, and stability that gives rise to a particular phenotype has limited the identification of traits acquired through evolution. This is further complicated by the fact that mutations are pleiotropic, and interactions between mutations are not always understood. Antibiotic resistance mediated by beta-lactamases represents an evolutionary paradigm in which organismal fitness depends on the catalytic efficiency of a single enzyme. Based on this, we have dissected the structural and mechanistic features acquired by an optimized metallo-beta-lactamase (MbetaL) obtained by directed evolution. We show that antibiotic resistance mediated by this enzyme is driven by 2 mutations with sign epistasis. One mutation stabilizes a catalytically relevant intermediate by fine tuning the position of 1 metal ion; whereas the other acts by augmenting the protein flexibility. We found that enzyme evolution (and the associated antibiotic resistance) occurred at the expense of the protein stability, revealing that MbetaLs have not exhausted their stability threshold. Our results demonstrate that flexibility is an essential trait that can be acquired during evolution on stable protein scaffolds. Directed evolution aided by a thorough characterization of the selected proteins can be successfully used to predict future evolutionary events and design inhibitors with an evolutionary perspective.