The problem of finding optimal replacement strategies for certain classes of failure systems is considered. These systems can be repaired upon failure, but are stochastically deteriorating, i.e., the lengths of the operating intervals decrease in some sense, whereas the durations of the repairs increase. For several models of this type optimal replacement strategies are derived under natural assumptions on the reward and the cost structure.