Governing business compliance with regulations, laws, best practices, contracts, and the like is not an easy task, and so far there are only limited software products available that help a company to express compliance rules and to analyze its compliance state. We argue that today’s SOA-based way of implementing and conducting business (e.g., using Web services and business process engines) lends itself very well to the development of a comprehensive compliance government solution that effectively aids companies in being compliant. In this paper, we contextualize the compliance problem in SOA-based businesses, we highlight which are the most salient research challenges that need to be addressed, and we describe our approach to compliance governance, spanning design, execution, and evaluation concerns.