The basal actinopterygians comprise four major lineages (polypteriforms, acipenseriforms, lepisosteids, and Amia) and have been collectively called "ancient fish." We investigated the phylogeny of this group of fishes in relation to teleosts using mitochondrial genomic (mitogenomic) data, and compared this to the various alternative phylogenetic hypotheses that have been proposed previously. In addition to the previously determined complete mitochondrial DNA (mtDNA) sequences from 14 teleosts and two outgroups, we used newly determined mitogenomic sequences of 12 purposefully chosen species representing all the ancient fish lineages plus related teleosts. This data set comprised concatenated nucleotide sequences from 12 protein-coding genes (excluding the ND6 gene and third codon positions) and 22 transfer RNA (tRNA) genes (stem regions only) and these data were subjected to maximum parsimony, maximum likelihood, and Bayesian analyses. The resultant trees from the three methods were well resolved and largely congruent, with most internal branches being supported by high statistical values. Mitogenomic data strongly supported not only the monophyly of the teleosts (osteoglossomorphs and above), but also a sister-group relationship between the teleosts and a clade comprising the acipenseriforms, lepisosteids, and Amia, with the polypteriforms occupying the most basal position in the actinopterygian phylogeny. Although the tree topology differed from any of the previously proposed hypotheses based on morphology, it exhibited congruence with a recently proposed novel hypothesis based on nuclear markers.