Cloud- and service-oriented computing paradigms are intrinopaque to their users, as they cannot inspect providers’ implementations, and important concerns about aspects like security, compliance, dependability can arise. Therefore, users have to make trust decisions with respect to software providers, with the hope that there will not be any detrimental consequences. To contrast this situation, the paper proposes a framework to define, assess, monitor and make explicit the elements of a service that render it trustworthy. This paper relies on a number of recent scientific contributions, and aims at supporting informed decisions on obscure service implementations by machine-understandable statements about their objective (trustworthiness) characteristics. Such statements would innovate upon many aspects of service operations, from discovery to composition, deployment and monitoring. To demonstrate this, the paper presents a concept for a Trustworthy Service Marketplace.