The difficulties in climate change negotiations together with the recent withdrawal of the U.S. from the Paris Agreement call for new cooperative mechanisms to enable a resilient international response. In this study we propose an approach to aid such negotiations based on quantifying the benefits of interregional cooperation and distributing them among the participants in a fair manner. Our approach is underpinned by advanced optimisation techniques that automate the screening of millions of alternatives for differing levels of cooperation, ultimately identifying the most cost-effective solutions for meeting emission targets. We apply this approach to the Clean Power Plan, a related act in the U.S. aiming at curbing carbon emissions from electricity generation, but also being withdrawn. We find that, with only half of the states cooperating, the cost of electricity generation could be reduced by US$41 billion per year, while simultaneously cutting carbon emissions by 68% below 2012 levels. These win–win scenarios are attained by sharing the emission targets and trading electricity among the states, which allows exploiting regional advantages. Fair sharing of dividends may be used as a key driver to spur cooperation since the global action to mitigate climate change becomes beneficial for all participants. Even if global cooperation remains elusive, it is worth trying since the mere cooperation of a few states leads to significant benefits for both the U.S. economy and the climate. These findings call on the U.S. to reconsider its withdrawal but also boost individual states to take initiative even in the absence of federal action.