Although adequate resolution of higher-level relationships of organisms apparently requires longer DNA sequences than those currently being analyzed, limitations of time and resources present difficulties in obtaining such sequences from many taxa. For fishes, these difficulties have been overcome by the development of a PCR-based approach for sequencing the complete mitochondrial genome (mitogenome), which employs a long PCR technique and many fish-versatile PCR primers. In addition, recent studies have demonstrated that such mitogenomic data are useful and decisive in resolving persistent controversies over higher-level relationships of teleosts. As a first step toward resolution of higher teleostean relationships, which have been described as the "(unresolved) bush at the top of the tree," we investigated relationships using mitogenomic data from 48 purposefully chosen teleosts, of which those from 38 were newly determined during the present study (a total of 632,315 bp), using the above method. Maximum-parsimony and maximum-likelihood analyses were conducted with the data set that 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) from the 48 species. The resultant two trees from the two methods were well resolved and largely congruent, with many internal branches supported by high statistical values. The tree topologies themselves, however, exhibited considerable variation from the previous morphology-based cladistic hypotheses, with most of the latter being confidently rejected by the mitogenomic data. Such incongruence resulted largely from the phylogenetic positions or limits of long-standing problematic taxa, which were quite unexpected from previous morphological and molecular analyses. We concluded that the present study provided a basis of and guidelines for future investigations of teleostean evolutionary mitogenomics and that purposeful higher-density taxonomic sampling, subsequent sequencing efforts, and phylogenetic analyses of their mitogenomes may be decisive in resolving persistent controversies over higher-level relationships of teleosts, the most diversified group of all vertebrates, comprising over 23,500 extant species.