Low fertilizer application rates for several decades have depleted soil nutrients in Sub-Saharan Africa (SSA) and contributed to relatively stagnant maize ( Zea mays L.) yields. As maize is a staple crop, nutrient depletion has resulted in major food insecurity. While one potential solution is to apply more nitrogen (N) fertilizer, previous studies in SSA have found maize yield responses to be variable, likely because N is often not the only limiting nutrient. This study aimed to determine the impact of consecutive N fertilizer applications on plant uptake and available soil reserves of non-N nutrients. Maize was grown continuously in 3 sites that were representative of the ecosystem variability found in East/Southern Africa (Embu, Kenya; Kiboko, Kenya; Harare, Zimbabwe) at 4 different N fertilizer rates (0–160 kg N ha−1) from 2010 to 2015. Following the final season, grain, stover, and soil (sampled at different depths to 0.9 m) samples were analyzed for essential plant nutrients. Nitrogen fertilizer increased plant uptake of P, S, Cu, and Zn by up to 280%, 320%, 420%, and 210%, respectively, showing potential for mitigating non-N nutrient deficiencies in 2 of the 3 sites. Cumulatively, however, there was a net negative effect of higher N rates on the P, K, and S soil-plant balances in all sites and on the Mn and Cu soil-plant balance in Kiboko, indicating that applying N fertilizer depletes non-N soil nutrients. While N fertilizer enhances the uptake of non-N nutrients, a balanced application of multiple essential nutrients is needed to sustainably increase yields in SSA. Electronic supplementary material The online version of this article (10.1007/s10705-019-10016-1) contains supplementary material, which is available to authorized users.