Reliability of mobile cloud computing system (MCS) components substitution is an important issue for troubleshooting and system upgrading. In this paper, MCS components substitution is equated to MCS service substitution based on a service-oriented architecture of MCS. Then, a reliable workflow for MCS service substitution is proposed, which consists of two parts. One is a qualitative judgment method for MCS service substitution according to the relationship between service compatibility and substitution, based on S-T Pi-calculus with space operator and time operator. The other is a series of substitution processes from the judgment results above, based on service management theory. Finally, a case study is performed to show that how to apply the workflow to ensure MCS components' reliable substitution. The experiment result demonstrates that this workflow is reasonable and feasible.