Abstract: A QoS-substitution model with composition-supported is developed, since the traditional substitution models are unavailable due to lack of transactional support in the execution process of Web service. In the model, the interrelation between many kinds of services and characteristics of Web service for a certain business are all fully considered. Combining the composition cost for a failed or unavailable service with that to substitute the same one in the whole execution process of Web service, an objective QoS function is provided to evaluate comprehensively the composition-supported service that will be substituted. Then, a new QoS-driven service substitution algorithm supported by composition is proposed. Testing results demonstrated that the model proposed not only ensures the atomicity and data consistency in the service substitution process, but also improves the reliability and of service systems.