Cloud computing represents a promising computing paradigm, where computational power is provided similar to utilities like water, electricity or gas. While most of the Cloud providers can guarantee some measurable non-functional performance metrics e.g., service availability or throughput, there is lack of adequate mechanisms for guaranteeing certifiable and auditable security, trust, and privacy of the applications and the data they process. This lack represents an obstacle for moving most business relevant applications into the Cloud. In this paper we devise a novel approach for compliance management in Clouds, which we termed Compliant Cloud Computing (C3). On one hand, we propose novel languages for specifying compliance requirements concerning security, privacy, and trust by leveraging domain specific languages and compliance level agreements. On the other hand, we propose the C3 middleware responsible for the deployment of certifiable and auditable applications, for provider selection in compliance with the user requirements, and for enactment and enforcement of compliance level agreements. We underpin our approach with a use case discussing various techniques necessary for achieving security, privacy, and trust in Clouds as for example data fragmentation among different protection domains or among different geographical regions.