The aim of the study was to evaluate the content, occurrence, and leachability of arsenic (As), lead (Pb), and thallium (Tl) in wastes from coal cleaning processes with respect to the safe management of this waste. The study focused on wastes resulting from the wet gravitation and flotation processes employed for the purposes of coking coal cleaning in four coal mines situated in the Upper Silesian Coal Basin (Poland). The scope of the study included (i) determination of the content of these elements in the investigated wastes using atomic absorption spectrometry, (ii) evaluation of their mode of occurrence using electron microprobe analysis, and (iii) preliminary assessment of their leachability in deionized water. The content of the analyzed elements in the examined samples of coal waste was twice as high as the average content of these elements in the Earth's crust. The contents of As and Pb, however, did not exceed their permissible contents in inert waste in accordance with Polish legal regulations based on EU directives. The limit on the content of Tl is not specified by these regulations, but its amount in the examined samples was similar to that occurring in the soils. Moreover, leaching tests have shown that these elements are hardly eluted from the analyzed material. Their content in the water leachates was generally lower than the detection limit of the analytical method, complying with the standards for good and very good water quality. Low leachability of these elements most probably results from their mode of occurrence in the investigated wastes. The chemical analysis using an electron microprobe and the analysis of the correlation between these elements, e.g., total and pyritic sulfur, have shown that Pb, As, and Tl are mainly found in sulfide minerals which are characterized by negligible solubility. In conclusion, the investigated hard coal processing waste does not constitute a threat to the environment and can be commercially used or safely neutralized, e.g., by landfilling.