In this paper, we generalize a multi-state element (MSE) replacement optimization problem to multi-state systems (MSS), in which a global optimal MSE replacement policy is obtained to achieve better outcome than local optimal MSE replacement strategy which does not consider the system performance rate dependency. It can be also concluded from the illustrative case of a power station coal transportation system that performance rate dependency has a significant impact on MSS maintenance decision making. The methodology proposed in this paper has insights to engineers to understand the importance of performance rate dependency and provides a general framework for MSS maintenance optimization.