Reliability is an issue of importance in Web service applications, as they often expose an enterprise's critical processes, such as finance, insurance, customer-relationship management, or sales. Reliability can be ensured by providing compensations for faults, but the complexity of the applications makes it impossible to anticipate all the scenarios that the applications might encounter. An approach to error tolerance needs to be provided. In this chapter we show that even when on-line applications are complex, the service-oriented architecture of Web services provides an excellent basis for our redundancy-based approach to error tolerance. Our studies and theories in software robustness demonstrate that: (i) robustness can be achieved through redundancy; (ii) by being able to represent and conciliate multiple viewpoints, agents are an appropriate unit for adding redundancy; and (iii) agents having different algorithms but similar responsibilities can produce the needed redundancy. We integrate Web services as part of the functionality of the agents that provide the redundancy.