Extant jawed vertebrates, or gnathostomes, fall into two major monophyletic groups, namely chondrichthyans (cartilaginous fishes) and osteichthyans (bony fishes and tetrapods). Fossil representatives of the osteichthyan crown group are known from the latest Silurian period, 418 million years (Myr) ago, to the present. By contrast, stem chondrichthyans and stem osteichthyans are still largely unknown. Two extinct Palaeozoic groups, the acanthodians and placoderms, may fall into these stem groups or the common stem group of gnathostomes, but their relationships and monophyletic status are both debated. Here we report unambiguous evidence for osteichthyan characters in jaw bones referred to the late Silurian (423-416-Myr-old) fishes Andreolepis hedei and Lophosteus superbus, long known from isolated bone fragments, scales and teeth, and whose affinities to, or within, osteichthyans have been debated. The bones are a characteristic osteichthyan maxillary and dentary, but the organization of the tooth-like denticles they bear differs from the large, conical teeth of crown-group osteichthyans, indicating that they can be assigned to the stem group. Andreolepis and Lophosteus are thus not only the oldest but also the most phylogenetically basal securely identified osteichthyans known so far.