Increased conformational flexibility is the prevailing explanation for the high catalytic efficiency of cold-adapted enzymes at low temperatures. However, less is known about the structural determinants of flexibility. We reported two novel cold-adapted zinc metalloproteases in the thermolysin family, vibriolysin MCP-02 from a deep sea bacterium and vibriolysin E495 from an Arctic sea ice bacterium, and compared them with their mesophilic homolog, pseudolysin from a terrestrial bacterium. Their catalytic efficiencies, k_cat/K_m (10–40 °C), followed the order pseudolysin < MCP-02 < E495 with a ratio of ∼1:2:4. MCP-02 and E495 have the same optimal temperature (T_opt, 57 °C, 5 °C lower than pseudolysin) and apparent melting temperature (T_m = 64 °C, ∼10 °C lower than pseudolysin). Structural analysis showed that the slightly lower stabilities resulted from a decrease in the number of salt bridges. Fluorescence quenching experiments and molecular dynamics simulations showed that the flexibilities of the proteins were pseudolysin < MCP-02 < E495, suggesting that optimization of flexibility is a strategy for cold adaptation. Molecular dynamics results showed that the ordinal increase in flexibility from pseudolysin to MCP-02 and E495, especially the increase from MCP-02 to E495, mainly resulted from the decrease of hydrogen-bond stability in the dynamic structure, which was due to the increase in asparagine, serine, and threonine residues. Finally, a model for the cold adaptation of MCP-02 and E495 was proposed. This is the first report of the optimization of hydrogen-bonding dynamics as a strategy for cold adaptation and provides new insights into the structural basis underlying conformational flexibility.