Combining community needs and preferences with dryland plant expertise in order to select suitable native species for large-scale natural capital restoration is the approach that has been successful in the Sahel as part of Africa’s Great Green Wall program. In order to increase plant diversity and restore degraded land, we investigated four cross-border regions of Mali, Burkina Faso, and Niger, all located in dryland ecosystems of the Sahel. In 120 beneficiary village communities, with a total population of over 50,000 farmers, including 51% women, participatory diagnostic meetings were conducted, leading to the selection of 193 plant species, most of which were mainly used for food, medicine, fodder, and fuel. Of these, 170 were native and considered suitable for enriching and restoring those village lands. The most environmentally well-adapted and economically relevant species were prioritized, quality seeds were collected, and nursery seedlings were produced under technical supervision of villages. From 2013 to 2015, 55 woody and herbaceous species were planted to initiate restoration of 2,235 ha of degraded land. On average, 60% of seedlings survived and grew well in the field after three rainy seasons. Due to its multiple uses, including gum arabic production, Acacia senegal was preferred by local people in most cases, accounting for 30% of seedlings planted. Such promising results, in an effort to restore degraded land for and with the help of thousands of farmers, could not have been achieved without the combination of scientific plant expertise and efficient rural capacity development, underpinned by high levels of community engagement.