Soil nutrient depletion is one of the major causes of high yield gaps and nutrient defciencies in East Africa highlands, including Rwanda. This research sought to determine the current soil nutrient balance and its spatial variation in 10 Rwandan agro-ecological zones. Soil nitrogen (N), phosphorus (P) and potassium (K) depletion in croplands were calculated using data from 455 feld trials of the Optimizing Fertilizer Recommendations in Africa (OFRA) project in Rwanda. Calculated soil nutrient balances (NPK) and 15 environmental covariates were used to calibrate soil nutrient depletion models using ensemble machine learning (EML) and 10-fold crossvalidation. In the 2019–2020 growing season, annual N and K depletions were 33.6 kg N ha− 1 yr− 1 and 71.0 kg K ha− 1 yr− 1, with a positive P balance of 2.30 kg P ha− 1 yr− 1. High soil nutrient uptake and high soil nutrient loss due to erosion and leaching were two main causes of NPK depletion. Spatial variations of NPK balance were influenced by soil nutrient stocks, soil erosion, elevation, rainfall, soil texture, and soil bulk density. The 10-fold cross-validation showed that coeffcients of determination (R2) of NPK models were 62%, 58%, and 58%, respectively. Compared to single models, ensemble machine learning improved NPK model accuracy up to 5%. Our research revealed that soil nutrient depletion was highest in the northwest and lowest in the southeast of the study area. We conclude that increasing soil nutrient inputs without reducing soil nutrient loss due to soil degradation will not decrease soil nutrient depletion in Rwanda and ensemble machine learning outperforms single models in predicting soil nutrient balance. The solution to reduce high soil nutrient depletion in all agroecological zones of Rwanda would be to prioritize soil and water conservation measures and increase soil nutrient inputs.