Coal fly ash (CFA) is a predominant waste by-product of coal combustion which is disposed of in open ash dams that utilize large pieces of land. This waste material is classified as a hazardous substance in South Africa as well as in other countries due to its fine particles that are easily blown to the atmosphere and the unacceptable levels of heavy metals and persistent organic pollutants. Contaminants in CFA can pollute surface and ground water, agricultural sites, soil and therefore pose risks to the health of humans and the environment. More than 500 million tons of CFA is produced yearly and over 200 million tons remain unused globally. The production will continue due to high consumer energy demands, especially in countries with heavy reliance on coal for power generation. Despite a significant progress made on the application of phytoremediation approach for decontamination of polluted sites, there is very limited evidence for its potential in the rehabilitation of CFA dumps. Low organic carbon, microbial activities and availability of nutrients including nitrogen contribute to restricted plant growth in CFA, and therefore converting ash dumps to barren lands devoid of vegetation. Leguminous plant species can fix atmospheric nitrogen through symbiotic association with bacteria. Therefore, their intercropping mixture development can improve the chemistry of the substrate and facilitate nutrients availability to the companion plants. This approach can enhance the performance of phytoremediation and promote sustainable practices. The paper provides an overview of the ongoing burden of CFA disposal and discusses the ecological and economic benefits of using legumes, aromatic and bioenergy plants. We identify knowledge gaps to establishing vegetation in ash dumping sites, and provide insights to encourage continued research that will enhance the applicability of phytoremediation in restoration programs.