Carbon offset projects through forestation are employed within the emissions trading framework to store carbon. Yet, information about the potential of landscapes to stock carbon, essential to the design of offset projects, is often lacking. Here, based on data on vegetation carbon, climate and soil, we quantify the potential for carbon storage in woody vegetation across tropical Africa. The ability of offset projects to produce co-benefits for ecosystems and people is then quantified. When co-benefits such as biodiversity conservation are considered, the top-ranked sites are sometimes different to sites selected purely for their carbon-stocking potential, although they still possess up to 92% of the latter carbon-stocking potential. This work provides the first continental-scale assessment of which areas may provide the greatest direct and indirect benefits from carbon storage reforestation projects at the smallest costs and risks, providing crucial information for prioritization of investments in carbon storage projects.