We examine the problem of optimally maintaining a stochastically degrading system using preventive and reactive replacements. The system's rate of degradation is modulated by an exogenous stochastic environment process, and the system fails when its cumulative degradation level first reaches a fixed deterministic threshold. The objective is to minimize the total expected discounted cost of preventively and reactively replacing such a system over an infinite planning horizon. To this end, we present and analyze a Markov decision process model. It is shown that, for each environment state, there exists an optimal threshold-type replacement policy. Additionally, empirical evidence suggests that, when the environment process is monotone, and the state-dependent degradation rates are totally ordered, the optimal threshold is monotone. Lastly, we derive closed-form bounds on the optimal thresholds.