Metal ions at the active site of an enzyme act as cofactors, and their dynamic fluctuations can potentially influence enzyme activity. Here, we use lambda-exonuclease as a model enzyme with two Mg2+ binding sites and probe activity at various concentrations of magnesium by single-molecule-FRET. We find that while Mg-A(2+) and Mg-B(2+) have similar binding constants, the dissociation rate of Mg-A(2+) is two order of magnitude lower than that of Mg-B(2+) due to a kinetic-barrier-difference. At physiological Mg2+ concentration, the Mg-B(2+) ion near the 5'-terminal side of the scissile phosphate dissociates each-round of degradation, facilitating a series of DNA cleavages via fast product-release concomitant with enzyme-translocation. At a low magnesium concentration, occasional dissociation and slow re-coordination of Mg-A(2+) result in pauses during processive degradation. Our study highlights the importance of metal-ion-coordination dynamics in correlation with the enzymatic reaction-steps, and offers insights into the origin of dynamic heterogeneity in enzymatic catalysis.