This paper first hypothesizes that countries that have accumulated more statehood experience over the last two millennia tend to have more stringent climate change policies. A second hypothesis is that there are also indirect effects via the rule of law, democracy, corruption, political instability, regulatory quality, and government effectiveness. Our empirical evidence provides support for these hypotheses. An early start helps both directly and indirectly. The strongest indirect effects occur through government effectiveness, rule of law, and corruption. Climate change policy analysis may take these findings into account and incorporate state capacity building and bureaucratic and legal reforms into the design of international environmental agreements. However, the effects are unlikely to arrive quickly.