Major cloud providers have built geo-distributed infrastructures to serve global users. Regional electricity price variations of up to 100% create significant cost optimization opportunities through strategic cross-regional task placement. However, recent large-scale outages have underscored the catastrophic impact of failures in these complex, interdependent systems. Therefore, fault tolerance emerges as a critical concern in geo-distributed cloud environments. Existing geo-distributed task placement solutions primarily focus on cost optimization, largely ignoring fault tolerance. Meanwhile, traditional fault tolerance mechanisms are ill-suited for cross-regional environments, as they are vulnerable to region-level failures and fail to leverage geographical cost diversity. This paper introduces Fossil, a novel scheme designed to bridge this gap by holistically addressing both cost efficiency and fault tolerance in geo-distributed clouds. Fossil formulates the fault-tolerant task placement problem as a mixed-integer non-linear optimization problem and proposes a submodular-based approximation algorithm with a guaranteed performance bound of \(1-(1/e)\) . Extensive experiments on real-world datasets show that Fossil reduces electricity costs by up to 63% compared to existing solutions while significantly improving system reliability, reducing throughput degradation by up to 75.5% and improving MTTR by up to 98.78% under region-level failures.