Recent attempts at cooperating on climate change mitigation highlight the limited efficacy of large-scale agreements, when commitment to mitigation is costly and initially rare. Bottom-up approaches using region-specific mitigation agreements promise greater success, at the cost of slowing global adoption. Here, we show that a well-timed switch from regional to global negotiations dramatically accelerates climate mitigation compared to using only local, only global, or both agreement types simultaneously. This highlights the scale-specific roles of mitigation incentives: local incentives capitalize on regional differences (e.g., where recent disasters incentivize mitigation) by committing early-adopting regions, after which global agreements draw in late-adopting regions. We conclude that global agreements are key to overcoming the expenses of mitigation and economic rivalry among regions but should be attempted once regional agreements are common. Gradually up-scaling efforts could likewise accelerate mitigation at smaller scales, for instance when costly ecosystem restoration initially faces limited public and legislative support.