Fishes of the order Alepocephaliformes, slickheads and tubeshoulders, constitute a group of deep-sea fishes poorly known in respect to most areas of their biology and systematics. Morphological studies have found alepocephaliform fishes to display a mosaic of synapomorphic and symplesiomorphic characters, resulting in great difficulties when attempting to resolve intra- and interrelationships. Molecular data recently added to the confusion by removing Alepocephaliformes from the Euteleostei and placed them as incertae sedis within the Otocephala. In the present study we attempt to further clarify relationships of Alepocephaliformes by adding newly determined whole mitogenome sequences from 19 alepocephaliforms in order to address 1) phylogenetic position of Alepocephaliformes within the Otocephala; and 2) intrarelationships of Alepocephaliformes. The present study includes 96 taxa of which 30 are alepocephaliforms and unambiguously aligned sequences were subjected to partitioned maximum likelihood and Bayesian analyses. Results from the present study support Alepocephaliformes as a genetically distinct otocephalan order as sister clade to Ostariophysi (mostly freshwater fishes comprising Gonorynchiformes, Cypriniformes, Characiformes, Siluriformes and Gymnotiformes). The disputed family Bathylaconidae was found to be an artificial assemblage of the two genera Bathylaco and Herwigia, with the former as the sister group of the family Alepocephalidae and the latter nested within Alepocephalidae. Platytroctidae was found to be monophyletic as sister clade to the rest of Alepocephaliformes. Previously unrecognized clades within the family Alepocephalidae are presented and a clade comprising Alepocephalus, Conocara and Leptoderma was recovered as the most derived. As long as the current classification is being followed, the genera Alepocephalus, Bathytroctes, Conocara and Narcetes were all found non-monophyletic.