Abstract Data protection regulations like the General Data Protection Regulation (GDPR) are increasingly important in securing individuals’ privacy as society goes digital. The success of any regulation, however good, ultimately depends on how well it is executed. Existing literature fails to answer what good execution means in this context. We research what practitioners think are the objectives of data protection regulators and how they evaluate their effectiveness. We explore novel ways to assess regulator performance more systematically. We surveyed 70 chief information security officers and conducted 23 structured interviews. The interviewees included informed business executives, lawyers, digital rights activists, and four national regulators. We supplement it with an analysis of diverse enforcement databases. Our findings indicate a mismatch between the broad presumed objectives attributed to regulators and the narrow criteria used to judge them in practice. Perception of the regulator’s effectiveness is subjective, sanctions-focused, and influenced by one’s role and responsibilities. Moreover, the independence of regulators, intentionally designed to insulate them from daily politics, raises serious questions of accountability. We examine the historical, cultural, and organizational motivations behind the current byzantine complexity of the GDPR regime. Lastly, we contribute a series of key performance indicators and make structural suggestions around centralized and standardized reporting of cases to deliver improved learning, legitimacy, transparency, and comparability. We believe our findings have important implications for the future development of regulator assessment and accountability in Europe and in the growing number of GDPR-like regimes outside Europe.