We study the enzymatic degradation of an elastic fiber under tension using an anisotropic random-walk model coupled with binding-unbinding reactions that weaken the fiber. The fiber is represented by a chain of elastic springs in series along which enzyme molecules can diffuse. Numerical simulations show that the fiber stiffness decreases exponentially with two distinct regimes. The time constant of the first regime decreases with increasing tension. Using a mean field calculation, we partition the time constant into geometrical, chemical and externally controllable factors, which is corroborated by the simulations. We incorporate the fiber model into a multiscale network model of the extracellular matrix and find that network effects do not mask the exponential decay of stiffness at the fiber level. To test these predictions, we measure the force relaxation of elastin sheets stretched to 20% uniaxial strain in the presence of elastase. The decay of force is exponential and the time constant is proportional to the inverse of enzyme concentration in agreement with model predictions. Furthermore, the fragment mass released into the bath during digestion is linearly related to enzyme concentration that is also borne out in the model. We conclude that in the complex extracellular matrix, feedback between the local rate of fiber digestion and the force the fiber carries acts to attenuate any spatial heterogeneity of digestion such that molecular processes manifest directly at the macroscale. Our findings can help better understand remodeling processes during development or in disease in which enzyme concentrations and/or mechanical forces become abnormal.