Soil and nutrient losses due to soil erosion are pronounced in potato growing areas of East Africa due largely to the rugged topography and high soil disturbance associated with potato cultivation. This study intercropped potato (Solanum tuberosum L.) with three grain legumes: lablab bean (Lablab purperous L.), garden pea (Pisum sativa L.) and climber bean (Phaseolus vulgaris L.) in runoff plots and assessed their impact on soil and nutrient losses in central Kenya highlands. Bare plots and sole potato stands were included as controls. Vegetal cover was measured at different potato growth stages while runoff and soil loss were quantified at every runoff generating event and used for nutrient analyses. Yields were expressed as potato equivalents (PEY) at the end of each season. Mean cumulative sediment yield decreased from 169 t/ ha in sole potato plots to 50–83 t/ ha in potato-legume intercropping, representing a reduction of 51–70%. The eroded sediment exported in large quantity the SOC (16.6–39.5 kg C ha−1 yr−1), N (5.5–29.8 kg N ha−1 yr−1), P (3.9–16.4 kg P ha−1 yr−1) and K (5.2–14.6 kg K ha−1 yr−1) and were consistently higher in sole potato plots relative to potato-legume intercropping. These losses occurred mainly at potato emergence following fertilizer application. Stronger associations of sediment nutrient enrichments was found with the micro-aggregates (250–50 μm) than with the macro-aggregates (>250 μm) pointing to the different degree of nutrient mobilization and distribution in eroded sediment. The PEY were significantly greater in potato-lablab bean system than in sole potato, while intercropping with garden pea and climber bean showed similar PEY to that of sole potato, suggesting that potato-lablab system may be preferred by the smallholder farmers. These results justify the need to intercrop potato with indeterminate legume intercrops, a strategy that must be done in a way guaranteeing high yield stability to the smallholder farmers.