The Osteostraci are currently regarded as the sister taxon to jawed vertebrates and, as such, osteostracan phylogeny, notably their hypothetical ancestral morphotype, has far reaching ramifications for early vertebrate evolution. The polarity of the group and the monophyly and interrelationships of the proposed constituent clades have not been tested. Here a new phylogeny is proposed for the Thyestiida, the most controversial and informative of the five main orders of Osteostraci. A comprehensive global parsimony approach is applied for the first time. The monophyly of the group, including genera of suspected thyestiid affinities, is firmly demonstrated, as is the monophyly of some constituent groups such as the Siberian Tannuaspidinae. The phylogeny supports the proposals of Janvier (1985a‐c) and is inconsistent with previous ‘Tremataspis‐basal’ models of Osteostracan evolution. Application of the phylogeny to the stratigraphical record demonstrates an early evolution and origin for the Osteostraci and indicates a missing fossil record for the group in the Llandovery, strongly related to facies bias.