Anthropogenic climate change constitutes one of the most far-reaching problems of global justice, most importantly in terms of distributional and intergenerational justice. By now, there is a large body of literature discussing various principles that could in theory form the basis for a just international climate regime. However, most of these studies come from a political theory or philosophical background and focus on an ideal solution to address climate change. They tend to neglect practical political constraints and consequences as well as the procedural dimension of justice. In this paper, we make the case for the importance of procedural justice in ethical debates over climate change. We argue that linking the climate justice literature to three more practical oriented conceptions of justice, namely non-domination, impartiality and mutual recognition, and how they link up with international and world society, we can come to a more thorough understanding of the political implications of climate justice. We illustrate the added value of our approach by contrasting the Kyoto Protocol to the Paris Agreement, and by comparing EU engagement before Copenhagen with EU efforts towards Paris.