Discourse analysis is gaining attention in transition studies. This paper uses discourse network analysis (DNA) to study how discourse coalitions, and the storylines they mobilize, change over time. Drawing from archival data of two daily newspapers, we analyze the struggle over coal phase-out in Germany (2000–2020). We identify an anti-coal discourse coalition, which was stable and ideationally congruent over time. It used climate change as the dominant storyline to delegitimize coal. The phase-out policy decision in 2020 can be interpreted as the success of this coalition. The pro-coal coalition, in contrast, was more dispersed and less consistent in their arguments. Nonetheless, it was able to institutionalize some of their key storylines in the final policies. We argue that DNA is a powerful tool we can mobilize in sustainability transitions research for the study of politics and beyond.