The Acanthomorpha is the largest group of teleost fishes with about one third of extant vertebrate species. In the course of its evolution this lineage experienced several episodes of radiation, leading to a large number of descendant lineages differing profoundly in morphology, ecology, distribution and behavior. Although Acanthomorpha was recognized decades ago, we are only now beginning to decipher its large-scale, time-calibrated phylogeny, a prerequisite to test various evolutionary hypotheses explaining the tremendous diversity of this group. In this study, we provide new insights into the early evolution of the acanthomorphs and the euteleost allies based on the phylogenetic analysis of a newly developed dataset combining nine nuclear and mitochondrial gene markers. Our inferred tree is time-calibrated using 15 fossils, some of which have not been used before. While our phylogeny strongly supports a monophyletic Neoteleostei, Ctenosquamata (i.e., Acanthomorpha plus Myctophiformes), and Acanthopterygii, we find weak support (bootstrap value < 48%) for the traditionally defined Acanthomorpha, as well as evidence of non-monophyly for the traditional Paracanthopterygii, Beryciformes, and Percomorpha. We corroborate the new Paracanthopterygii sensu Miya et al. (2005) including Polymixiiformes, Zeiformes, Gadiformes, Percopsiformes, and likely the enigmatic Stylephorus chordatus. Our timetree largely agrees with other recent studies based on nuclear loci in inferring an Early Cretaceous origin for the acanthomorphs followed by a Late Cretaceous/Early Paleogene radiation of major lineages. This is in contrast to mitogenomic studies mostly inferring Jurassic or even Triassic ages for the origin of the acanthomorphs. We compare our results to those of previous studies, and attempt to address some of the issues that may have led to incongruence between the fossil record and the molecular clock studies, as well as between the different molecular timetrees.