Trust is a crucial aspect for open distributed systems. Especially as users may rely on the shared services to make important decisions, it is essential to let them know services’ trustworthiness. Provenance describes the origins and processes that are related to the generation of services. It can greatly enhance transparency and accountability of shared services. In this paper, we focus on how to derive trust information from huge amount of provenance data, and proposed a case-based approach which can estimate services’ trustworthiness from provenance. This approach can greatly utilise the value of provenance, and provide more objective and reasonable trust estimation to users.