Implementing global climate change policies on the national and sub-national level requires the support of many societal actors. This support depends on the perceived legitimacy of climate policies, which can be sustained by legitimation debates in domestic news media. This article analyses legitimation statements on climate politics in newspapers of five countries for three Conferences of the Parties in 2004, 2009 and 2014 ( n = 369 legitimation statements). According to our data, it is mainly the legitimacy of international climate policies (instead of national ones) which is evaluated in national fora, and it is usually portrayed negatively. However, there is a noticeable shift in the arguments used over our 10-year period of analysis, moving from efficiency as the dominating evaluation criterion to questions of fairness in the distribution of costs and gains.