The increasing number of Web services and thus of possible combinations is particularly hard to accord with the dynamic and versatile feature of the Web. Indeed, in general, complex Web services may frequently happen not to fit the situation encountered. To avoid composing a new Web service “from scratch”, we search a practical way of repairing failed ones. This paper presents a Web service repairing heuristic based on a semantic modeling approach. Modeling Web services is triggered with an OWL-S fragment. Repairing is based on our previous work which allows organizing a collection of Web services into hierarchies. A NEXPTIME complexity upper bound is shown for a reparation which doesn't change the internal structure of the complex Web service.