Conservation agriculture is widely promoted for soil conservation and crop productivity increase, although rigorous empirical evidence from sub-Saharan Africa is still limited. This study aimed to quantify the medium-term impact of tillage (conventional and reduced) and crop residue management (retention and removal) on soil and crop performance in a maize–soybean rotation. A replicated field trial was started in sub-humid Western Kenya in 2003, and measurements were taken from 2005 to 2008. Conventional tillage negatively affected soil aggregate stability when compared to reduced tillage, as indicated by lower mean weight diameter values upon wet sieving at 0–15 cm (PT <0.001). This suggests increased susceptibility to slaking and soil erosion. Tillage and residue management alone did not affect soil C contents after 11 cropping seasons, but when residue was incorporated by tillage, soil C was higher at 15–30 cm (PT*R = 0.037). Lack of treatment effects on the C content of different aggregate fractions indicated that reduced tillage and/or residue retention did not increase physical C protection. The weak residue effect on aggregate stability and soil C may be attributed to insufficient residue retention. Soybean grain yields tended to be suppressed under reduced tillage without residue retention, especially in wet seasons (PT*R = 0.070). Consequently, future research should establish, for different climatic zones and soil types, the critical minimum residue retention levels for soil conservation and crop productivity.