Web service compositions are exposed to a wide variety of failures. The service components re- motely located can represent potential problems due to the means of connectivity necessary for communication or because of changes implemented by their respective provider during system updates. Those problems represent unexpected events that compromise the correctness and availability of a given service composition. This dissertation presents an approach to improve the robustness of Web service compositions by recovering from failures occurred at different moments of their execution. We first present a taxonomy of failures as an overview of previous research works on the topic of fault recovery of service compositions. The resulting classifica- tion is used to propose our self-healing method for Web service orchestrations. The proposed method, based on the refinement process of compositions, takes user preferences into account to generate the best possible recovering compositions. To validate our approach, we produced a prototype implementation capable of simulating and analyzing different scenarios of faults. For that matter, our work introduces algorithms for generating synthetic compositions and Web services. In this setting, both the recovery time and the user preference degradation are investigated under different strategies, namely local, partial or total recovery. These strategies represent different levels of intervention on the composition.