Although the order Gonorynchiformes includes only 31 species assigned to seven genera and four families, it exhibits a large variety of anatomical structures, making difficult the reconstruction of phylogenetic relationships among its representatives. Within the basal teleosts, the Gonorynchiformes belong to the Otocephala where they have been alternatively placed as the sister group of the Otophysi and of the Clupeiformes. In this context, we investigated the phylogeny of the Gonorynchiformes using whole mitogenome sequences from 40 species (six being newly determined for this study). Our taxonomic sampling included at least one species of each gonorynchiform genus and of each other major otocephalan lineage. Unambiguously aligned, concatenated mitogenomic sequences (excluding the ND6 gene and control region) were divided into five partitions (1st, 2nd, and 3rd codon positions, tRNA genes, and rRNA genes) and partitioned Bayesian analyses were conducted. The resultant phylogenetic trees were fully resolved, with most of the nodes well supported by the high posterior probabilities. As expected, the Otocephala were recovered as monophyletic. Within this group, the mitogenome data supported the monophyly of Alepocephaloidei, Gonorynchiformes, Otophysi, and Clupeiformes. The Gonorynchiformes and the Otophysi formed a sister group, rending the Ostariophysi monophyletic. This result conflicts with previous mitogenomic phylogenetic studies, in which a sister relationship was found between Clupeiformes and Gonorynchiformes. We discussed the possible causes of this incongruence. Within the Gonorynchiformes, the following original topology was found: (Gonorynchus (Chanos (Phractolaemus (Cromeria (Grasseichthys (Kneria, Parakneria)))))). We confirmed that the paedomorphic species Cromeria nilotica and Grasseichthys gabonensis belong to the family Kneriidae; however, the two species together did not form a monophyletic group. This result challenges the value of reductive or absent characters as synapomorphies in this group.