The phylogeny of otocephalan fishes is the subject of broad controversy based on morphological and molecular evidence. The primary unresolved issue pertaining to this lineage relates to the origin of Characiphysi, especially the paraphyly of Characiformes. The considerable uncertainty associated with this lineage has precluded a greater understanding of the origin and evolution of the clade. Herein, a phylogenomic approach was applied to resolve this debate. By analyzing 10 sets of transcriptomic data generated in this study and 12 sets of high-throughput data available in public databases, we obtained 1,110 single-copy orthologous genes (935,265 sites for analysis) from 22 actinopterygians, including 14 otocephalan fishes from six orders: Clupeiformes, Gonorynchiformes, Cypriniformes, Siluriformes, Characiformes, and Gymnotiformes. Based on a selection of 125 nuclear genes screened from single-gene maximum likelihood (ML) analyses and sequence bias testing, well-established relationships among Otocephala were reconstructed. We suggested that Gymnotiformes are more closely related to Characiformes than to Siluriformes and Characiformes are possibly paraphyletic. We also estimated that Otocephala originated in the Early-Late Jurassic, which postdates most previous estimations, and hypothesized scenarios of the early historical biogeographies of major otocephalan lineages.