The relationships among and within the main lineages of the order Clupeiformes have been explored in few morphological studies and still remain poorly understood. Using whole mitogenome sequences, we inferred the relationships among 25 clupeiform species, sampled from each clupeiform family and subfamily, and a large selection of non-clupeiform teleosts. Our character sets, including unambiguously aligned, concatenated mitogenome sequences that we have divided into four (1st and 2nd codon positions, tRNA genes, and rRNA genes) or five partitions (same as before plus the transversions at 3rd codon positions, using 'RY' coding), were analyzed by the partitioned Bayesian method. The result strongly supported the monophyly of the Clupeiformes within the Otocephala, with Denticeps clupeoides as the sister group of a clade comprising all the remaining clupeiforms species (= suborder Clupeoidei). Within the Clupeoidei, the family Engraulidae was the sister group of the remaining taxa, comprising members of Sundasalangidae, Pristigasteridae, Clupeidae and Chirocentridae. Relationships among the latter four families remained ambiguous. In particular, the position of the Chirocentridae was difficult to estimate possibly owing to its higher molecular evolutionary rate. Of the five subfamilies in the family Clupeidae, monophylies of three (Alosinae, Clupeinae and Dorosomatinae) were statistically rejected. Instead, our mitogenomic data provide strong support for new clades within the Clupeidae, some of which are composed of members of more than one of the previously accepted subfamilies.