Although policy complexity has been identified as one of the major challenges for the EU both by practitioners and EU scholars, the complexity of EU law is rarely measured and studied systematically. In this paper, we trace the complexity of EU policies from the days of the European Communities up to the present day and investigate the extent to which various rounds of EU enlargement and treaty revisions have impacted upon the complexity of the EU’s secondary legislation. Our analysis is built on a novel index of policy complexity that relies on a computer-based measurement approach, covering textual aspects of technicality, indeterminacy, institutional differentiation and density. The original dataset contains information on the complexity of the initial policy proposal and final text of all decision-making procedures available in the EUR-Lex database, aggregating data of more than 50,000 legal texts nested within approximately 30,000 legislative procedures between 1965 and 2019. Our data thus allow us to assess how policy complexity varies over time as well as across legislative procedures and policy areas. At a theoretical level, we hypothesize that, controlling for policy-specific factors, the evolution of policy complexity should be jointly driven by power shifts in the EU’s institutional architecture (treaty revisions) and changes in the number of veto players (enlargement). The paper has important implications for comparative political science, as it provides us with a broader understanding of the ways in which political institutions shape the complexity of public policies.