Industrial and mining waste dumping is among the most concerning anthropogenic causes of the formation of stress-laden wastelands, which are characterized by loss of plant cover and subsequent land degradation. Under the pressure of changing climate, the revival of the degraded wastelands into productive lands becomes a sustainable option to meet the basic survival demands of the increasing human population. Restoration of vegetation cover is a widely accepted eco-friendly approach for remediation of degraded wastelands over physical or chemical strategies. However, the successful establishment of plants in wastelands is a difficult process due to the phytotoxic nature of the wasteland soils. Therefore, the use of naturally growing native plants, which thrive well in the adverse soil properties of degraded lands with little or no agronomical effort, is an effective option. Some of these plants might have phytoremediation potential, which is a sustainable technology for the remediation of contaminants including heavy metals from soil and water by using plants. Documentation of such stress-tolerant naturally growing plants of various wastelands and studying their mechanism of tolerance are among the major emerging areas of research in recent times. Such efforts may help in finding novel plant species that are more stress-tolerant with greater potential of creating vegetation cover on degraded wastelands. Therefore, for the benefit of interested researchers and policymakers, an attempt has been made to review and comprehensively document the discrete information, from available sources, on naturally growing native plants of various industrial and mining wastelands, their stress management strategies and phytoremediation prospects in changing climate.