Web services run in a highly dynamic environment, as a result, the QoS of which will change relatively frequently.In order to make the composite service adapt to such dynamic property of Web services, we propose a self-healing approach for web service composition. Such an approach is an integration of backing up in selection and reselecting in execution. In order to make the composite service heal itself as quickly as possible and minimize the number of reselections, a way of performance prediction is proposed in this paper. On this basis, the self-healing approach is presented including framework,the triggering algorithm of the reselection and the reliability model of the service. Experiments show that the proposed solutions have better performance in supporting the self-healing Web service composition.