The mechanisms by which climate and vegetation affect erosion rates over various time scales lie at the heart of understanding landscape response to climate change. Plot-scale field experiments show that increased vegetation cover slows erosion, implying that faster erosion should occur under low to moderate vegetation cover. However, demonstrating this concept over long time scales and across landscapes has proven to be difficult, especially in settings complicated by tectonic forcing and variable slopes. We investigate this problem by measuring cosmogenic Be-10-derived catchment-mean denudation rates across a range of climate zones and hillslope gradients in the Kenya Rift, and by comparing our results with those published from the Rwenzori Mountains of Uganda. We find that denudation rates from sparsely vegetated parts of the Kenya Rift are up to 0.13 mm/yr, while those from humid and more densely vegetated parts of the Kenya Rift flanks and the Rwenzori Mountains reach a maximum of 0.08 mm/yr, despite higher median hillslope gradients. While differences in lithology and recent land-use changes likely affect the denudation rates and vegetation cover values in some of our studied catchments, hillslope gradient and vegetation cover appear to explain most of the variation in denudation rates across the study area. Our results support the idea that changing vegetation cover can contribute to complex erosional responses to climate or land-use change and that vegetation cover can play an important role in determining the steady-state slopes of mountain belts through its stabilizing effects on the land surface.