The main challenges faced in the reclamation of severely degraded lands are in the management of the systems and finding plant species that will grow under the harsh conditions common in degraded soils. This is especially important in extremely adverse situations found in some substrates from mining activities or soils that have lost their upper horizons. Under these conditions, recolonization of the area by native vegetation through natural succession processes may be extremely limited. Once the main physical and chemical factors restrictive to plant growth are corrected or attenuated, the introduction of leguminous trees able to form symbioses with nodulating N₂-fixing bacteria and arbuscular mycorrhizal fungi constitutes an efficient strategy to accelerate soil reclamation and initiate natural succession. These symbioses give the legume species a superior capacity to grow quickly in poor substrates and to withstand the harsh conditions presented in degraded soils. In this article we describe several successful results in Brazil using N₂-fixing legume tree species for reclamation of areas degraded by soil erosion, construction and mining activities, emphasizing the potential of the technique to recover soil organic matter levels and restore ecosystem biodiversity and other environmental functions.