Anthropogenic desertification is a problem that plagues drylands globally; however, the factors which maintain degraded states are often unclear. In Canyonlands National Park on the Colorado Plateau of southeastern Utah, many degraded grasslands have not recovered structure and function >40 yr after release from livestock grazing pressure, necessitating active restoration. We hypothesized that multiple factors contribute to the persistent degraded state, including lack of seed availability, surficial soil-hydrological properties, and high levels of spatial connectivity (lack of perennial vegetation and other surface structure to retain water, litter, seed, and sediment). In combination with seeding and surface raking treatments, we tested the effect of small barrier structures (“ConMods”) designed to disrupt the loss of litter, seed and sediment in degraded soil patches within the park. Grass establishment was highest when all treatments (structures, seed addition, and soil disturbance) were combined, but only in the second year after installation, following favorable climatic conditions. We suggest that multiple limiting factors were ameliorated by treatments, including seed limitation and microsite availability, seed removal by harvester ants, and stressful abiotic conditions. Higher densities of grass seedlings on the north and east sides of barrier structures following the summer months suggest that structures may have functioned as artificial “nurse-plants”, sheltering seedlings from wind and radiation as well as accumulating wind-blown resources. Barrier structures increased the establishment of both native perennial grasses and exotic annuals, although there were species-specific differences in mortality related to spatial distribution of seedlings within barrier structures. The unique success of all treatments combined, and even then only under favorable climatic conditions and in certain soil patches, highlights that restoration success (and potentially, natural regeneration) often is contingent on many interacting factors.