Web service technology provides basic infrastructure for deploying collaborative business processes. Web Service security standards and protocols aim to provide secure communication and conversation between service providers and consumers. Still, for a client calling a Web service it is difficult to ascertain that a particular service instance satisfies—at execution time—specific non-functional properties. In this paper we introduce the notion of certified Web service assurance, characterizing how service consumers can specify the set of security properties that a service should satisfy. Also, we illustrate a mechanism to re-check non-functional properties when the execution context changes. To this end, we introduce the concept of context-aware certificate, and describe a dynamic, context-aware service discovery environment.