Historical sheep farming in the Patagonian drylands has led to reduced grass cover, soil erosion, and shrub encroachment, compromising ecosystem function. Effective restoration requires managing shrub cover, bare soil, and patch connectivity through various strategies. This study evaluates rehabilitation interventions in a grass-steppe ecosystem, comparing grazed and ungrazed areas. Over three years, we tested the following: (a) mechanical shrub cutting with biomass redistribution, and (b) enhancing patch connectivity with Pinus spp. branch piles, alongside controls, in eighteen 5 m × 5 m plots invaded by Mulinum spinosum. Half of the plots were fenced to exclude grazing, resulting in six treatment combinations. We monitored soil properties, vegetation cover, and species composition. The treatments explained twice as much of the variation in community composition as the annual climatic variations (0.26 vs. 0.13). Livestock exclusion increased perennial grass cover more than the grazed plots did (2.14 vs. 1.42 times the initial measure). All treatments reduced the amount of bare soil except the grazed controls. Shrub cutting, especially with grazing, increased the lasting litter coverage by 5–10% and decreased the bare soil equivalently. Organic matter increased except in the non-intervened interpatches (0.95 times). The enclosures with cut shrubs trapped erodible particles, showing a 5% increase. Our study highlights that grazing destabilizes communities, while enclosures stabilize them, with interventions improving soil fertility and mitigating erosion.