The content of policy proposals changes to varying extents over the course of the legislative process. In some instances, the text introduced by the agenda setter is almost left untouched by the decision-makers; in other cases, the final act hardly resembles the initial proposal. Yet, despite its strong relevance for the field of legislative politics, the question of how this variance can be explained is still unresolved. In this paper, we contribute to a better understanding of how legislative proposals evolve before they become law by focusing on changes in their complexity. Specifically, we investigate how the complexity of more than 2,000 policy proposals adopted by the European Commission between 1994 and 2020 changed during their respective legislative negotiations. We employ a text-as-data approach to measure several indicators of policy complexity, track the changes of these indicators as the Commission proposals move through the EU’s legislative process and analyze the degree to which institutional and political factors help to explain the existing variance in complexity change. In particular, we put our theoretical focus on the inclusiveness of the decision-making process and on the preference heterogeneity of the involved political actors. The analysis thus adopts an innovative perspective on the analysis of legislative negotiations and sheds new light on the crucial question of how legislative institutions and political actors jointly shape the complexity of policy output.