Restoration of degraded subtropical succulent thicket, via the planting of Portulacaria afra (spekboom) truncheons, is the focus of a public works programme funded by the South African government. The goals of the programme, which started in 2004, are to create jobs, sequester carbon, restore biodiversity, reduce erosion, improve soil water holding capacity and catalyse private sector investment for upscaling of restoration. Here we report on a region-wide experiment to identify factors that can improve project success. Measures of success were survivorship and annual aboveground biomass carbon sequestration (ABCsr) of spekboom truncheons some 33–57 months after planting—starting in March 2008—into 173 fenced plots (0.25 ha) located throughout the global extent of spekboom thicket vegetation. We also collected data for 18 explanatory variables under the control of managers, and an additional 39 variables reflecting soil physical and chemical characteristics and rainfall patterns post restoration, all beyond the influence of managers. Since the latter covariates were available for only 83 plots, we analysed the two data sets separately. We used a prediction rule ensemble to determine the most important predictors of restoration success. There was great variation in percentage survivorship (median = 24, range = 0–100%) and ABCsr (median = 0.009, range = 0–0.38 t C ha−1 yr−1). The model using management variables explained less variance (53%) in survivorship than the model incorporating additional soil and rainfall covariates (62%). ABCsr models were better fits (78 and 88% variance explained, respectively). All model configurations identified browse intensity as a highly influential predictor of restoration success. Predicted success was highest for plots located in target habitat; however, only 45% were thus located, suggesting the need for expert input and habitat modelling for improving target habitat identification. Frost exposure was another important predictor influencing all models but was likely a consequence of locating sites off target habitat. Sites planted on equatorward slopes during the warm season showed reduced carbon sequestration, possibly due to elevated soil moisture stress associated with high radiation loads. Physiographic factors associated with improved restoration success were location on sloping ground (reduced frost exposure), increasing longitude (more warm-season rainfall) and increasing latitude (less frost coastwards). Few trends were evident among post-restoration climatic factors beyond the control of managers. Higher rainfall during the year post restoration had a negative impact on carbon sequestration while higher rain during the early months post restoration had a positive effect on both carbon sequestration and survivorship. Soil factors showed little importance for the survivorship model, whereas silt content, % K and Mg CEC emerged as predictors of carbon sequestration. Our results have direct relevance for improving the success of landscape-scale restoration projects envisioned for the ca. 8,930 km2 of degraded spekboom thicket.