To study the geochemical characteristics of 11 environmentally sensitive trace elements in the coals of the Permian Period from the Huainan coalfield, Anhui province, China, borehole samples of 336 coals, two partings, and four roof and floor mudstones were collected from mineable coal seams. Major elements and selected trace elements were determined by inductively coupled plasma optical emission spectrometry (ICP-OES), inductively coupled plasma mass spectrometry (ICP-MS), and hydride generation atomic absorption spectrometry (HAAS). The depositional environment, abundances, distribution, and modes of occurrence of trace elements were investigated. Results show that clay and carbonate minerals are the principal inorganic constituents in the coals. A lower deltaic plain, where fluvial channel systems developed successively, was the likely depositional environment of the Permian coals in the Huainan coalfield. All major elements have wider variation ranges than those of Chinese coals except for Mg and Fe. The contents of Cr, Co, Ni, and Se are higher than their averages for Chinese coals and world coals. Vertical variations of trace elements in different formations are not significant except for B and Ba. Certain roof and partings are distinctly higher in trace elements than underlying coal bench samples. The modes of occurrence of trace elements vary in different coal seams as a result of different coal-forming environments. Vanadium, Cr, and Th are associated with aluminosilicate minerals, Ba with carbonate minerals, and Cu, Zn, As, Se, and Pb mainly with sulfide minerals.