Negative nitrogen balance represents a major factor causing low potato yield in potato growing areas of Kenya while its excessive surplus poses a significant environmental concern. In order to synchronize this tradeoff, a field trial integrating potato (Solanum tuberosum L.) with lima bean (Phaseolus lunatus L.) and dolichos (Lablab purpureus L.) in intercropping system was conducted in the upper midland [1552 m above sea level (masl), lower highland (1894 masl) and upper highland (2552 masl)] agro-ecological zones of Kenya. Nitrogen gains from mineralization, fertilization, biological fixation, and outputs from biomass accumulation, leaching, volatilization and soil erosion were quantified using standard procedures. Soil N balance ranged from − 10.7 to − 18.1 kg N ha−1 for sole potato, 4.1 to 6.6 kg N ha−1 for intercropping and 2.9 to 22.3 kg N ha−1 for sole legumes. The intermediate range of polyphenol and lignin contents in intercropping enhanced N mineralization with peak N release of 8 to 9 kg N ha−1 matching with peak N uptake by potato (19.9 to 31.2 kg N ha−1). Nitrate was leached below the active root zone in sole potato cropping (4.2 to 46.6 kg N ha−1), a process that was diverged by the deep root systems of legume intercrops. These results suggest that legume intercropping can provide a means of balancing the nitrogen retained in the biomass and soil, thus offering a mechanism for optimizing the soil N balance in smallholder potato farming systems