Teleost fishes are the largest and most diverse group of extant vertebrates. They are divided into three major lineages - the Osteoglossomorpha (bonytongues and mooneyes), Elopomorpha (eels and relatives) and Clupeocephala (all the remaining teleosts). The phylogenetic relationship between these three groups has not been resolved satisfactorily. Mitogenome-based phylogenetic studies have placed Osteoglossomorpha as the most ancestral teleost group, with Elopomorpha and Clupeocephala forming a monophyletic group. On the other hand, recent studies based on nuclear genes as well as ultraconserved elements have suggested Elopomorpha as the most ancestral teleost group. We have sequenced the whole-genome of an Osteoglossomorph, the Asian arowana (Scleropages formosus) which has a 780 Mb genome and predicted 22,016 protein-coding genes. We carried out phylogenomic analysis using a genome-wide set of one-to-one orthologues obtained from arowana, several other teleosts, spotted gar and coelacanth. Our analysis of this large set of protein sequences supported a sister group relationship between Osteoglossomorpha and Elopomorpha, with Clupeocephala constituting an outgroup, in contrast to the relationships proposed by previous analyses based on smaller datasets.