Continuous cultivation of potato (Solanum tuberosum L.) in monoculture systems represents the greatest factor deteriorating soil organic matter (SOM) in smallholder farms. With an aim to breaking this norm, a 2-year field trial intercropping potato with two legumes: lima bean (Phaseolus lunatus) and dolichos (Lablab purpureus), was conducted in the upper-midland (1552 meters above sea level (masl.)), lower-highland (1854 masl.) and upper-highland (2552 masl.) agro-ecologies of Kenya. Residues from each cropping system were quantified at the end of each season and incorporated back into the soil at start of the subsequent season. A combined physical and density fractionation was used to separate the soil in macro-aggregates (>250 μm), micro-aggregates (250–50 μm) and silt plus clay fractions (<50 μm), while SOM was partitioned into labile (density of 1.65 to 1.85 g cm−3) and stable (2.60 g cm−3) fractions. Microbial biomass contents were determined by chloroform fumigation while enzymatic activities were assessed by hydrolyses of fluorescein diacetate and dehydrogenase. Compared to sole potato, intercropping increased the contents of light fraction organic matter by 12–28%, dissolved organic matter by 7–21% and microbial biomass by 15–38%, thus stimulating enzyme activities. Trends in soil microbial respiration followed those of enzyme activity and were 20–34% higher in intercropping than in sole potato. Intercropping ensured high residue returns which got short-term residence within the macro-aggregates, thus ensuring steady supply of substrates to the soil microbes. These results affirm legume intercropping as a possible entry point to restoring the impoverished soil quality in smallholder potato farming systems.