Comprising more than 800 extant species, the class Cephalopoda (octopuses, squid, cuttlefish, and nautiluses) is a fascinating group of marine conchiferan mollusks. Recently, the first cephalopod genome (of Octopus bimaculoides) was published, providing a genomic framework, which will enable more detailed investigations of cephalopod characteristics, including developmental, morphological, and behavioural traits. Meanwhile, a robust phylogeny of the members of the subclass Coleoidea (octopuses, squid, cuttlefishes) is crucial for comparative and evolutionary studies aiming to investigate the group's traits and innovations, but such a phylogeny has proven very challenging to obtain. Here, we present the results of phylogenetic inference at the genus level using mitochondrial and nuclear marker sequences available from public databases. Topologies are presented which show support for (1) the monophyly of the two main superorders, Octobrachia and Decabrachia, and (2) some of the interrelationships at the family level. We have mapped morphological characters onto the tree and conducted molecular dating analyses, obtaining congruent results with previous estimates of divergence in major lineages. Our study also identifies unresolved phylogenetic relationships within the cephalopod phylogeny and insufficient taxonomic sampling among squids excluding the Loliginidae in the Decabrachia and within the Order Cirromorphida in the Octobrachia. Genomic and transcriptomic resources should enable resolution of these issues in the relatively near future. We provide our alignment as an open access resource, to allow other researchers to reconstruct phylogenetic trees upon this work in the future.