Because of its tremendous temporal and spatial scope, climate change poses profound regulatory issues. Significant transboundary effects and spatially differentiated effects make it highly desirable that international regulatory mechanisms are utilised in order to arrive at effective mitigation and adaptation solutions. Yet, the different spaces that states occupy in terms of causation and effect makes agreement on what must be regulated through international mechanisms and indeed how to regulate such subject matter. Consequently, this paper proposes that legitimacy needs to be considered one of the core concerns of international climate change regulation and governance. The aim of this paper is to clarify the role of the concept of legitimacy in international climate change regulation, and to set forth a specific discursive approach aimed at identifying legitimacy-enhancing design features for internationally regulating climate change.