Endochondral bone is the main internal skeletal tissue of nearly all osteichthyans—the group comprising more than 60,000 living species of bony fishes and tetrapods. Chondrichthyans (sharks and their kin) are the living sister group of osteichthyans and have primarily cartilaginous endoskeletons, long considered the ancestral condition for all jawed vertebrates (gnathostomes). The absence of bone in modern jawless fishes and the absence of endochondral ossification in early fossil gnathostomes appear to lend support to this conclusion. Here we report the discovery of extensive endochondral bone in Minjinia turgenensis, a new genus and species of ‘placoderm’-like fish from the Early Devonian (Pragian) of western Mongolia described using X-ray computed microtomography. The fossil consists of a partial skull roof and braincase with anatomical details providing strong evidence of placement in the gnathostome stem group. However, its endochondral space is filled with an extensive network of fine trabeculae resembling the endochondral bone of osteichthyans. Phylogenetic analyses place this new taxon as a proximate sister group of the gnathostome crown. These results provide direct support for theories of generalized bone loss in chondrichthyans. Furthermore, they revive theories of a phylogenetically deeper origin of endochondral bone and its absence in chondrichthyans as a secondary condition.