The European Union’s General Data Protection Regulation (EU-GDPR) has initiated a paradigm shift in data protection toward greater choice and sovereignty for individuals and more accountability for organizations. Its strict rules have inspired data protection regulations in other parts of the world. However, many organizations are facing difficulty complying with the EU-GDPR: these new types of data protection regulations cannot be addressed by an adaptation of contractual frameworks, but require a fundamental reconceptualization of how companies store and process personal data on an enterprise-wide level. In this paper, we introduce the resource-based view as a theoretical lens to explain the lengthy trajectories towards compliance and argue that these regulations require companies to build dedicated, enterprise-wide data management capabilities. Following a design science research approach, we propose a theoretically and empirically grounded capability model for the EU-GDPR that integrates the interpretation of legal texts, findings from EU-GDPR-related publications, and practical insights from focus groups with experts from 22 companies and four EU-GDPR projects. Our study advances interdisciplinary research at the intersection between IS and law: First, the proposed capability model adds to the regulatory compliance management literature by connecting abstract compliance requirements to three groups of capabilities and the resources required for their implementation, and second, it provides an enterprise-wide perspective that integrates and extends the fragmented body of research on EU-GDPR. Practitioners may use the capability model to assess their current status and set up systematic approaches toward compliance with an increasing number of data protection regulations.