Climate change is predicted to alter the distributions of tropical tuna stocks in the Pacific Ocean. Recent modelling projects significant future shifts in tuna biomass from west to east, and from national jurisdictions to high seas areas. As the distributions of these stocks change, the relevant regional fisheries management organisations (RFMOs)—the Western and Central Pacific Fisheries Commission (WCPFC) and the Inter-American Tropical Tuna Commission (IATTC)—will need to develop an expanded framework for cooperation and collaboration to fulfil their conservation and management responsibilities under international law. The key elements of a possible expanded framework for cooperation can be developed, and fundamental areas for collaboration identified, by applying and adapting principles established in the United Nations Convention on the Law of the Sea, the United Nations Fish Stocks Agreement, and the constituent instruments of the RFMOs themselves. Our analysis reveals a wide range of important issues requiring cooperation, and three clear priorities. First, a formal mechanism for cooperation is needed to enable effective and efficient decision-making and action by the two RFMOs on key issues. Second, further cooperation is required in scientific research and modelling to better understand the biology and distributions of Pacific tuna stocks and how they will respond to climate change, and to inform stock assessments and harvest strategies. Third, the RFMOs must cooperate to define appropriate limits on fishing for each stock in a way that ensures they are compatible across the two organisations, taking into account their different members and management regimes.