Morphology of the leaves of stem compressions originally attributed to Protolepidodendron scharyanum from the Middle Devonian of North Xinjiang, China is reinvestigated. The leaf is three-dimensional, consisting of one central abaxial segment and four lateral adaxial segments, and does not conform to the once bifurcate leaf of Protolepidodendron. Specimens are therefore transferred to Leclercqia cf. L. complexa. This is the first unequivocal report of the genus Leclercqia in China based on complete leaf morphology. The distribution of Leclercqia is discussed, demonstrating a more or less cosmopolitan genus in the Middle Devonian. The Middle Devonian flora of North Xinjiang shows great similarity to that of Venezuela and North America, and almost no relationship with that of Yunnan, South China.