Lack of flexible and cost-effective fault tolerance mechanism is one of major obstacles for enhancing availability and efficiency of cloud application systems. We propose a novel fault tolerance as a service scheme, where cloud applications utilize suitable fault tolerance service as specific added services, such as the live migration of virtual machines, software rejuvenation, and real-time failure detection, to be worked cooperatively with cloud applications themselves. Our proactive fault tolerance as a service scheme tends to achieve promising improvements on the high availability for cloud applications.