Carbon (C) offset projects through forestation are employed within the emissions trading framework to store C. Yet, information about the potential of landscapes to stock C, essential to the design of offset projects, is often lacking. Based on data on vegetation C, climate and soil we quantified the potential for C storage in woody vegetation across tropical Africa. The ability for offset projects to produce co-benefits for ecosystems and local communities was also investigated. When co-benefits such as biodiversity conservation were considered, the top-ranked sites were often different to sites selected purely for their C stocking potential, but they still possessed 68% of the latter’s C stocking potential. This work provides the first continental-scale assessment of which areas may provide the greatest direct and indirect benefits from C storage reforestation projects at the smallest costs and risks, providing crucial information for prioritization of investments in C storage projects.