Cacao–based agroforestry systems are promoted as adaptation and mitigation solutions for cacao production and carbon sequestration. Based on a 20-year experiment, we assessed the impact of associated shade tree legume (ATL), Albizia lebbeck and Acacia mangium on the total carbon stock (in soil at 60 cm depth + tree biomass + litter) of cacao stands. This study included cacao systems shaded with either A. lebbeck (Cacao-Alb) or A. mangium (Cacao-Aca) and full-sun cacao stands (Control). Soil organic carbon (SOC) contents (up to 60 cm deep) were estimated by a calibrated near-infrared spectroscopy model. Total tree biomasses were estimated using allometric equations. Leaf litter was sampled from 1-m2 quadrats. Compared to Control, Cacao-Aca had a significant negative impact on the carbon stock in the cacao biomass (−47%) as well and in the soil at depths of 10 cm (−23%), 30 cm (−21%) and 60 cm (−12%). In contrast, Cacao-Alb had a nonsignificant effect on carbon storage in the cacao biomass, whereas it generally had a positive influence on the SOC stock regardless of depth, i.e., +6% at the 0–10 cm depth, +7% at 0–30 cm, +20% at 30–60 cm and + 11% at 0–60 cm. Cacao-Aca had a significant positive impact (+71%) on the total carbon stock per hectare. The increase in Cacao-Alb relative to that in the Control reached +38%, but the difference was not significant. These contrasting results between the two tree legume species could be explained by the high-quality litter, reflected by the lower C/N and C/P ratios produced by A. lebbeck, and the greater negative impact of A. mangium on cacao biomass. The main finding of this study is that the impact of intercropping cacao with shade tree legumes on the stand-level total carbon stock depends on the ATL species.