Rangeland degradation, typified by extensive bare ground and soil erosion, is a serious problem around the world. In sub-Saharan Africa, rangeland degradation threatens the food security of millions of people who depend on livestock and the region's large mammalian wildlife diversity. We tested the ability of five simple, low-cost erosion barriers to promote grass and forb establishment in a bare ground-dominated rangeland in Kenya. These treatments were: (1) trenches with small berms; (2) bundles of branches; and bundles of branches with (3) elephant dung balls, (4) burlap sacking, or (5) nylon mesh sacking inside them. We also tested whether barrier performance depended on (1) supplemental seeding with the grass Cenchrus ciliaris and (2) whether a barrier was located next to existing vegetation patches versus in the open. Within months, the trench and nylon mesh barriers had accumulated 20–50% more sediment than other treatments and had greater grass and forb seedling establishment. Seeding with Cenchrusresulted in higher herbaceous cover but was not necessary for other grasses to establish. After 3 years, the trench and nylon mesh barriers had created patches of new vegetation averaging 18–63% larger than patches created by the other treatments. Barriers that were initially adjacent to existing vegetation had created new vegetation patches averaging 65% larger than those created by solitary barriers. Results suggest that all barrier types increase grass cover but that trenches—especially if placed next to existing vegetation patches—are a particularly cost-effective way to reduce bare ground and erosion in degraded rangelands.