Distributed applications composed of collections of Web Services may call for diverse levels of reliability in different parts of the system. Byzantine fault tolerance (BFT) is a general strategy that has recently been shown to be practical for the development of certain classes of survivable, client-server, distributed applications; however, little research has been done on incorporating it into selective parts of multi-tier, distributed applications like Web Services that have heterogeneous reliability requirements. To understand the impacts of combining BFT and Web Services, we have created Thema, a new BFT middleware system that extends the BFT and Web Services technologies to provide a structured way to build Byzantine-fault-tolerant, survivable Web Services that application developers can use like other Web Services. From a reliability perspective, our enhancements are also novel in that they allow Byzantine-fault-tolerant services: (1) to support the multi-tiered requirements of Web Services, and (2) to provide standardized Web Services support for their own clients (through WSDL interfaces and SOAP communication). In this paper we study key architectural implications of combining BFT with Web services and provide a performance evaluation of Thema using the TPC-W benchmark.