Living species of Cephalopoda are classified into two main lineages, Nautiloidea and Coleoidea. Within the latter, two main groups are distinguished, Octopodiformes and Decapodiformes. Phylogenetic relationships within Coleoidea have been the subject of numerous studies and the relative phylogenetic position of several enigmatic groups, such as Vampyromorpha, Idiosepioidea and Spirulida, among others, has been contentious. Here, we reconstruct the phylogeny of Cephalopoda using all (39) currently reported complete mitochondrial (mt) genomes; in addition, we concatenated available partial mt genes from five important lineages (represented by genera Opisthoteuthis, Argonauta, Japetella, Thaumeledone and Spirula) that lack complete mt genomes, in order to include them in the phylogenetic analyses. The reconstructed trees recovered the monophyly of Octopodiformes (Octopoda + Vampyromorpha), of Octopoda and of Decapodiformes. Within Octopoda, the first split was between Cirrata and Incirrata and, within the latter, between Argonautoidea and Octopodoidea. Within Octopodoidea, the family Octopodidae, as traditionally defined, was nonmonophyletic. Within Decapodiformes, Sepiida were recovered sister to a clade including Idiosepiida as the first-diverging lineage. Among the remaining lineages of this clade, Myopsina were recovered sister to a ‘pelagic’ clade including Bathyteuthoidea, Spirulida and Oegopsida, to the exclusion of Sepiolida. Based on this fully resolved phylogeny, we inferred the evolution of gene rearrangements among the studied mitochondrial genomes, following a tandem duplication and random loss model. Finally, a chronogram was estimated under an uncorrelated relaxed molecular clock, which gave estimates of dates of major cladogenetic events within Cephalopoda that were considerably younger than those in previous studies.