The catalytic functions of metalloenzymes are often strongly correlated with metal elements in the active sites. However, dioxygen-activating nonheme quercetin dioxygenases (QueD) are found with various first-row transition-metal ions when metal swapping inactivates their innate catalytic activity. To unveil the molecular basis of this seemingly promiscuous yet metal-specific enzyme, we transformed manganese-dependent QueD into a nickel-dependent enzyme by sequence- and structure-based directed evolution. Although the net effect of acquired mutations was primarily to rearrange hydrophobic residues in the active site pocket, biochemical, kinetic, X-ray crystallographic, spectroscopic, and computational studies suggest that these modifications in the secondary coordination spheres can adjust the electronic structure of the enzyme-substrate complex to counteract the effects induced by the metal substitution. These results explicitly demonstrate that such noncovalent interactions encrypt metal specificity in a finely modulated manner, revealing the underestimated chemical power of the hydrophobic sequence network in enzyme catalysis.