Accurate species phylogenies are a prerequisite for all evolutionary research. Teleosts are the largest and most diversified group of extant vertebrates, but relationships among their three oldest extant lineages remain unresolved. On the basis of seven high-quality new genome assemblies in Elopomorpha (tarpons, eels), we revisited the topology of the deepest branches of the teleost phylogeny using independent gene sequence and chromosomal rearrangement phylogenomic approaches. These analyses converged to a single scenario that unambiguously places the Elopomorpha and Osteoglossomorpha (arapaima, elephantnose fish) in a monophyletic sister group to all other teleosts, i.e., the Clupeocephala lineage (zebrafish, medaka). This finding resolves more than 50 years of controversy on the evolutionary relationships of these lineages and highlights the power of combining different levels of genome-wide information to solve complex phylogenies.