Mining exploitation in the Mediterranean Basin has left evident scars on the environment, and poses serious risks for human health and biodiversity, especially when mine wastes are left abandoned. This review analysed the main issues of metal(loid)s pollution related to mine exploitation in the Mediterranean Basin. Here, a list of Mediterranean native plant species studied for phytoremediation is given and, considering their biological forms, vegetational types, and ecology, we categorised them into halotolerant and hydro/hygrophilous vegetation, annual and perennial meadows, garrigues and maquis, and high maquis and woods. The main conclusions of the review are as follows: (1) plant communities established on mine environments are often rich in endemic taxa which ensure a high biodiversity and landscape value, and can help in the psychophysical health of local inhabitants; (2) political and land management should take greater account of the use of native plants for the remediation of contaminated soils; (3) a multidisciplinary approach that includes, among others, studies on biochemical response to metal(loid)s as well as the application of innovative soil amendments gives better results; (4) phytoextraction applications require a detailed recovery plan that takes into consideration several issues, including the negative influence on biodiversity due to extensive use of monotypic plantations, disposal of harvested hazardous plants, and the risk of phytoextracts entering the food chain; and (5) more studies are necessary to increase knowledge and to detect suitable species—especially halophytic ones—for phytoremediation purposes.