Marine species are moving rapidly in response to warming, often in different directions and with variations dependent on location and depth. Given the current impetus to increase the area of protected ocean to 30%, conservation planning must include the 64% of the ocean beyond national jurisdictions, which in turn requires associated design challenges for conventional conservation to be addressed. Here we present a planning approach for the high seas that conserves biodiversity, minimizes exposure to climate change, retains species within reserve boundaries and reduces conflict with fishing. This is developed using data from across four depth domains, considering 12,932 vertebrate, invertebrate and algal species and three climate scenarios. The resultant climate-smart conservation areas cover 6% of the high seas and represent a low-regret option that provides a nucleus for developing a full network of high-seas marine reserves.