The Petalodontiformes are a small intriguing group of Permo–Carboniferous chondrichthyans. Petalodus is the longest known petalodont genus generally considered representative of the order. The first definite fossil record of seven well-preserved Petalodus teeth has been found in the Qianshi limestone in the Lower Permian (Cisuralian) middle–upper Taiyuan Formation in Yangquan City, Shanxi Province, North China. The specimens are characterized by petal-shaped teeth with a spade-like crown, and a long, tongue-shaped root; the crown is circled with a band or cingulum composed of imbricated ridges at the base. All seven teeth are assigned to the species P. ohioenesis because of their vertically narrow cingulum and much longer root. Petalodus is a worldwide genus, with fossil localities mainly concentrated in the Laurussia supercontinent. The occurrence of Petalodus teeth in Yangquan not only is the first fossil record in China, but also only the second record in Asia. The Yangquan fossil site was part of the paleoequatorial North China Craton during the Early Permian, and was isolated from Laurusia and East Gondwana by the Paleo-Tethys Ocean. The successful dispersal of Petalodus from Laurusia to the North China Block along Paleo-Tethys may support the possibility that Petalodus taxa were active free-swimmers rather than bottom dwellers. The new finding increases the petalodont diversity in eastern Asia, and also sheds new light on the distribution and stratigraphic range.