South Africa’s Succulent Karoo is home to unmatched numbers of dryland plant species. Unfortunately, decades of overstocking these rangelands with small livestock and historical ploughing for fodder have led to extensive degradation. Some areas are severely degraded, negatively affecting both agricultural livestock productivity and ecosystem health. Land degradation reduces land use options and leaves land users, and the ecosystems on which they depend, more vulnerable to environmental and economic stressors. Ecological restoration is promoted as an effective and cost-efficient option for building the resilience of local and regional ecosystems. However, dryland restoration confronts many environmental challenges that have limited its success to date. Here, we present the results of a local-scale participatory restoration trial and an assessment of the costs of regional-scale ecological restoration in the Nama Khoi area in Namaqualand, South Africa. In combination, these analyses are useful for identifying opportunities and barriers for the improved efficiency and effectiveness of dryland restoration. In Namaqualand, we find that ecological restoration is difficult and expensive. The expected impacts of climate change will only exacerbate these challenges. However, we argue that a holistic suite of land management actions that include sound management, the prevention of further degradation, and prudent investments in restoration even where costs are high is likely to be the only real option for sustaining land-based livelihoods in this region over the longer term.