Ginglymodi are a subgroup of holostean fishes, including living gars and their closely-related fossil taxa. The early Middle Triassic (Anisian, ~244 Ma) kyphosichthyiforms from Yunnan and Guizhou, China represent the earliest records of this clade. Here, we report the discovery of a new kyphosichthyiform fish, Yudaiichthys eximius gen. et sp. nov., on the basis of four well-preserved specimens from the second (upper) member of Guanling Formation in Luoping, eastern Yunnan. The new discovery stimulated a phylogenetic analysis to reassess the interrelationships of the Kyphosichthyiformes and their relationships with other early ginglymodians. Results of our analysis indicate that the previously defined family Kyphosichthyidae and the genus Sangiorgioichthys are paraphyletic. A revised Kyphosichthyiformes is proposed here, and it is divided into two families, Kyphosichthyidae and Lashanichthyidae fam. nov. The family Kyphosichthyidae is restricted to include two genera Kyphosichthys and Fuyuanichthys. The Chinese “Sangiorgioichthys” species are removed into a new genus Lashanichthys, which is recovered as a taxon sister to Yudaiichthys gen. nov., and both genera are grouped into the new family, Lashanichthyidae. Sangiorgioichthys is restricted to include two species (S. aldae and S. valmarensis) from the late Middle Triassic (Ladinian) of the Monte San Giorgio area. The genus is removed out of the Kyphosichthyiformes and is recovered as the sister taxon of the Semionotiformes-Lepisosteiformes clade. The revised topology provides new insights into the anatomical evolution during the earliest ginglymodian history.