Soil organic carbon (SOC) is an essential component, which soil quality depends on. Thus, understanding the spatial distribution and controlling factors of SOC is paramount to achieving sustainable soil management. In this study, SOC prediction for the Ourika watershed in Morocco was done using four machine learning (ML) algorithms: Cubist, random forest (RF), support vector machine (SVM), and gradient boosting machine (GBM). A total of 420 soil samples were collected at three different depths (0–10 cm, 10–20 cm, and 20–30 cm) from which SOC concentration and bulk density (BD) were measured, and consequently SOC stock (SOCS) was determined. Modeling data included 88 variables incorporating environmental covariates, including soil properties, climate, topography, and remote sensing variables used as predictors. The results showed that RF (R² = 0.79, RMSE = 1.2%) and Cubist (R² = 0.77, RMSE = 1.2%) were the most accurate models for predicting SOC, while none of the models were satisfactory in predicting BD across the watershed. As with SOC, Cubist (R² = 0.86, RMSE = 11.62 t/ha) and RF (R² = 0.79, RMSE = 13.26 t/ha) exhibited the highest predictive power for SOCS. Land use/land cover (LU/LC) was the most critical factor in predicting SOC and SOCS, followed by soil properties and bioclimatic variables. Both combinations of bioclimatic–topographic variables and soil properties–remote sensing variables were shown to improve prediction performance. Our findings show that ML algorithms can be a viable tool for spatial modeling of SOC in mountainous Mediterranean regions, such as the study area.