The potential environmental hazards posed by trace elements have assumed serious proportions due to their toxicity, bioavailability and geochemical behavior. The toxicity and mobility of trace elements in coal gangue is dependent on the elements’ chemical properties, therefore, the quantification of the different forms of trace elements is more significant than the estimation of their total concentrations. In this study, the mobility behavior of trace elements in coal gangue from the Huainan Coalfield was studied to evaluate the potential eco-toxicity of the trace elements. Sequential extraction was employed to analyze the fractionation behavior of trace elements in coal gangue. The selected trace elements (As, Co, Cr, Cu, Mn, Ni, Se, Sn, V and Zn) are predominantly found in silicate-bound, sulfide-bound and carbonate-bound fractions. The correlation of the element concentration with ash yield, aluminum, calcium and iron-sulfur indicates that As, Co, Cu, Ni, Se and Zn in coal gangue are mainly associated with sulfide minerals, which could release from coal gangue easily and can disperse into the environment as a result of long-term natural weathering. The Risk Assessment Code reveals that the trace elements (Mn, Cr, Se, Ni, Zn, As and Cu) can pose serious environmental risks to the ecosystem. The fractionation profiles of other elements (Co, Sn and V) indicate no risk or low risk to the environment.