We present the first analysis of cephalopod mitochondrial gene order and construct phylogenies based on gene order using Bayesian, distance, and parsimony analysis methods. Analyses included all species of cephalopod for which the whole mitochondrial genome has been sequenced. Where resolution was obtained, these analyses supported division of Neocoleoidea, in which all recent coleoid Cephalopoda can be placed, into Octopodiformes and Decapodiformes. For the same taxa, we also constructed a phylogeny in a maximum likelihood framework based on amino-acid coded sequence data of all mitochondrial protein coding genes. As well as supporting Octopodiformes and Decapodiformes, amino-acid analyses established support for Teuthoidea (Oegospida and Myopsida) to the exclusion of Sepiidae, and supported a monophyletic Oegopsida. Partial mitochondrial sequences of additional higher-level taxa for which whole genome data were not available were subsequently included in the amino-acid analysis to provide additional information on phylogeny. Spirulida was found to be basal amongst Decapodiformes. Mapping of morphological characters onto our phylogeny and consideration of palaeontological evidence suggests that our phylogeny reflects true evolutionary relationships. (C) 2011 The Linnean Society of London, Zoological Journal of the Linnean Society, 2011, 161, 573-586.