Recent attempts at cooperating on climate change mitigation highlight the limited efficacy of large-scale negotiations, when commitment to mitigation is costly and initially rare. Deepening existing voluntary mitigation pledges could require more stringent, legally-binding agreements that currently remain untenable at the global scale. Building-blocks approaches promise greater success by localizing agreements to regions or few-nation summits, but risk slowing mitigation adoption globally. Here, we show that a well-timed policy shift from local to global legally-binding agreements can dramatically accelerate mitigation compared to using only local, only global, or both agreement types simultaneously. This highlights the scale-specific roles of mitigation incentives: local agreements promote and sustain mitigation commitments in early-adopting groups, after which global agreements rapidly draw in late-adopting groups. We conclude that focusing negotiations on local legally-binding agreements and, as these become common, a renewed pursuit of stringent, legally-binding world-wide agreements could best overcome many current challenges facing climate mitigation.