We report a new genus and species of Paleonisciformes–Cretolepis dongbeiensis gen. et sp. nov., from the Early Cretaceous Longjiang Formation in Qiqihar City, Heilongjiang Province. The new materials can be distinguished from other Paleonisciformes genera by possessing the following characteristics: a sclerotic ring composed of more than five small bones; three pieces of suborbitals; one dermohyomandibular; a jaw hanging apparently inclined anteriorly; long and tall horizontal branch of the preopercular, a short vertical branch, with the angle formed by the two branches slightly higher than 90°; a triangular dorsal fin in the middle point between the pelvic and anal fins. The discovery of Mesozoic Paleonisciformes in northeastern China adds to the biodiversity and geographic distribution of Paleonisciformes.