Web service technology enables seamlessly integration of different software to fulfill dynamic business demands in a platform-neutral fashion. However, the adoption of loosely coupled and distributed services will cause trustworthiness problems. In this chapter, the authors present an experience-based evaluation of service's trustworthiness based on trust experience (understanding) and trust requirements (policy). The authors utilize ontology to specify past experiences of services and trustworthy requirement of requester. Before invoking found services, the addressed method can help requester evaluate the trustworthiness of the services based on his trustworthy requirements and past experiences of the services. Furthermore, they also present an evaluation method for composite services by taking the structure of the composite services into account. The main contribution of the paper is providing evaluation methods for Web services such that service requester can make better decision in selecting found services in terms of service's trustworthiness.