Teleost fishes comprise one-half of all vertebrate species and possess a duplicated genome. This whole-genome duplication (WGD) occurred on the teleost stem lineage in an ancient common ancestor of all living teleosts and is hypothesized as a trigger of their exceptional evolutionary radiation. Genomic and phylogenetic data indicate that WGD occurred in the Mesozoic after the divergence of teleosts from their closest living relatives but before the origin of the extant teleost groups. However, these approaches cannot pinpoint WGD among the many extinct groups that populate this 50- to 100-million-y lineage, preventing tests of the evolutionary effects of WGD. We infer patterns of genome size evolution in fossil stem-group teleosts using high-resolution synchrotron X-ray tomography to measure the bone cell volumes, which correlate with genome size in living species. Our findings indicate that WGD occurred very early on the teleost stem lineage and that all extinct stem-group teleosts known so far possessed duplicated genomes. WGD therefore predates both the origin of proposed key innovations of the teleost skeleton and the onset of substantial morphological diversification in the clade. Moreover, the early occurrence of WGD allowed considerable time for postduplication reorganization prior to the origin of the teleost crown group. This suggests at most an indirect link between WGD and evolutionary success, with broad implications for the relationship between genomic architecture and large-scale evolutionary patterns in the vertebrate Tree of Life.