Significant difference exists between things that work and things that work well. Availability along with reliability would make Web services the default technology of choice in developing many mission-critical electronic-business applications. Unfortunately, guaranteeing a Web service availability is still a challenge due to the unpredictable number of invocation requests a Web service (e.g., Google Maps) has to handle at a time, as well as the dynamic nature of the Internet (e.g., network disconnections). In addition, the heterogeneity, mobility and distributed nature of Web services makes traditional dependability and availability approaches inappropriate for Web services. In this paper, we describe the design of an on-demand replication approach for robust Web service provisioning. This approach dynamically deploys Web services at appropriate idle hosts, reducing the unavailability of Web services during peak demand for limited computing resources. In addition this approach promotes the decoupling of Web service providers and Web service host providers, which supports a more flexible replication model. © 2009 Springer Berlin Heidelberg.