Dependability is one of the most important challenges for service-oriented architectures if their success shall continue in critical settings such as air traffic control or finance and banking. Replication of services and the underlying resources is one of the primary fault tolerance techniques for achieving dependability. While replication is well known in traditional fields (e.g. databases), it is rather in its infancy in service-oriented environments. Thus, in order to reduce the dependability gap we are currently facing in service-oriented environments, we contribute with a replication middleware for Web services which is built upon the Java-based Axis2 SOAP engine and provides a variant of primary-backup replication. Performance evaluations of our middleware implementation show the relatively low overhead of replication if the number of replicas is small.