Soil organic carbon (SOC) plays a vital role in regulating climate, water supplies, and biodiversity, supporting key ecosystem services. However, SOC is highly vulnerable to human activities. Removal of crop residues accelerates SOC decline, especially when combined with conventional tillage—a common practice in communal areas of western Kenya and eastern Uganda, where residues are used as fodder or grazed. This study evaluated the impacts of conservation agriculture on SOC changes and its relationship with organic matter addition in Ferralsols of western Kenya (Bungoma and Trans-Nzoia) and eastern Uganda (Tororo and Kapchorwa). Maize (Zea mays) and beans (Phaseolus vulgaris) were grown, with mucuna (Mucuna pruriens) used as a cover crop to enhance soil cover and organic matter. Treatments included tillage systems—Minimum Tillage (MT), No-Till (NT), and Conventional Tillage (CT); nitrogen application (plus N and minus N); and cropping systems arranged in a split–split plot RCBD. Cropping systems comprised Current Practice (CP), Rotation 1 (ROT1), and Rotation 2 (ROT2). ROT1 involved maize–bean intercropping with mucuna relayed after bean harvest, while ROT2 used strip rotations of maize, beans, and mucuna. Fertilizers (DAP and CAN) supplied N and P. Soil pH, SOC, and total N were analyzed at each harvest. Results showed that CA-based tillage (MT and NT) with nitrogen increased SOC by about 28% and 26%, respectively, compared to CT in the 0–5 cm layer. ROT2 and ROT1 recorded higher SOC stocks than CP across depths. Nitrogen application significantly increased SOC, while SOC values were higher in surface layers than deeper profiles. The maize–mucuna–beans strip rotation improved SOC by ~13% over CP. MT,ROT2 plus N and NT,ROT2 plus N produced similar maize yields, whereas CT,ROT2 plus N yielded 13% less. MT-ROT2+N with residue retention is recommended for improved SOC and sustained productivity.