Pollution caused by hazardous and carcinogenic inorganic elements and organic compounds from coal may be more severe when coupled by other sources of pollution. In addition, the modes of occurrence of potential hazardous elements (PHEs) in coal cleaning rejects (CCRs) have been widely investigated using different methods, including statistical methods, which, however, in some cases resulted in misleading interpretations. In order to verify this potential problem and find an effective solution, we selected a data set, which contained comprehensive analyses of CCRs. The secondary products in sulphides-bearing coal mine rejects were studied in demand to determine their geochemical and ecological structures and to assess their position in the reduction of PHEs in the nature. A zone located in south Brazil, which is the major coal power plant in South America, can be given as an example of such a problem. In this work, a novel methodology for the analysis of PHEs in soils and sediments is proposed for this affected coal area. The analytical method combining X-Ray Diffraction (XRD) and advanced electron microscopies shows the importance of nanomineralogy in understanding different circumstances of coal contamination. Several ultrafine-nanoparticles (UNPs) were identified in the sampled soils and river sediments together with the PHEs. A decrease in PHEs was identified in association with UNPs. However, still further investigations are required with regard to the mobility of PHEs in water, atmosphere, soils, and sediments. The site studied around the coal power plant showed the highest sorption capacity possibly due to the high retention ability of components of soil and sediments such as carbon and clay. These observations of the coal-derived nanoparticles confirm their capability of regulating the mobility of hazardous elements, implying the need for restoring complex abandoned coal areas..