The Cloud Computing environments are susceptible to frequent failures as a result of their dynamic and unstable nature. Failures have a significant effect on cloud performance and on the benefits that customers and providers expect. Therefore, fault tolerance is necessary to mitigate the impact of failures and preventing revenue losses due to service level agreements (SLA) violation penalties. In this paper, we propose a fault tolerance directed by the SLA contracts established between cloud providers and customers. The proposed fault tolerance includes two phases, the first is based on the use of idles VMs according to selection strategies. The second phase is based on both advanced operation of degradation of quality of service and on VMs selection strategies. The advanced operation of degradation consists of beneficial combinations of VMs deallocation and allocation between customers leading to avoid SLA violation penalties. According to the experimental results, our proposed fault tolerance decreases by more than 10% the rate of considered SLA violations compared to existing approaches.