Soil organic carbon (SOC) stocks are critical for land management strategies and climate change mitigation. However, understanding SOC distribution in South Africa's arid and semi-arid regions remains a challenge due to data limitations, and the complex spatial and sub-surface variability in SOC stocks driven by desertification and land degradation. To support soil and land-use management practices, as well as advance climate change mitigation efforts, there is an urgent need to provide more precise SOC stock estimates within South Africa's arid and semi-arid regions. Hence, this study adopted remote-sensing approaches to determine the spatial sub-surface distribution of SOC stocks and the influence of environmental co-variates at four soil depths (i.e., 0-30 cm, 30-60 cm, 60-100 cm, and 100-200 cm). Using Extreme Gradient Boosting (XGBoost) and Random Forest (RF) regression-based algorithms, the study found the former (RMSE values ranging from 10.50 t/ha to 16.60 t/ha) to be a superior model of SOC than the latter (RMSE values ranging from 10.83 t/ha to 18.25 t/ha). Thereafter, using a variable importance analysis, the study demonstrated the influence of topo-climatic and soil texture on SOC stocks at different depths. The study further demonstrated that the top 100 cm of the soil profile contained more than 70 % of the total SOC stocks, with the topsoil (0-30 cm) accounting for 34 % of the total SOC. The models exhibited a general decreasing trend in SOC stocks across the first three soil depth intervals. Additionally, the study revealed substantial spatial variability in SOC stocks, with greater accumulation in the topsoil observed in central and northern regions, while deeper SOC storage was more pronounced in the eastern parts of the study area. Overall, these findings enhance the understanding of SOC dynamics in South Africa's arid and semi-arid landscapes and emphasizes the importance of considering site specific topo-climatic characteristics for sustainable land management and climate change mitigation.