The resolution of higher level phylogeny of the coleoid cephalopods (octopuses, squids, and cuttlefishes) has been hindered by homoplasy among morphological characters in conjunction with a very poor fossil record. Initial molecular studies, based primarily on small fragments of single mitochondrial genes, have produced little resolution of the deep relationships amongst coleoid cephalopod families. The present study investigated this issue using 3415 base pairs (bp) from three nuclear genes (octopine dehydrogenase, pax-6, and rhodopsin) and three mitochondrial genes (12S rDNA, 16S rDNA, and cytochrome oxidase I) from a total of 35 species (including representatives of each of the higher level taxa). Bayesian analyses were conducted on mitochondrial and nuclear genes separately and also all six genes together. Separate analyses were conducted with the data partitioned by gene, codon/rDNA, gene+codon/rDNA or not partitioned at all. In the majority of analyses partitioning the data by gene+codon was the appropriate model with partitioning by codon the second most selected model. In some instances the topology varied according to the model used. Relatively high posterior probabilities and high levels of congruence were present between the topologies resulting from the analysis of all Octopodiform (octopuses and vampire "squid") taxa for all six genes, and independently for the datasets of mitochondrial and nuclear genes. In contrast, the highest levels of resolution within the Decapodiformes (squids and cuttlefishes) resulted from analysis of nuclear genes alone. Different higher level Decapodiform topologies were obtained through the analysis of only the 1st+2nd codon positions of nuclear genes and of all three codon positions. It is notable that there is strong evidence of saturation among the 3rd codon positions within the Decapodiformes and this may contribute spurious signal. The results suggest that the Decapodiformes may have radiated earlier and/or had faster rates of evolution than the Octopodiformes. The following taxonomic conclusions are drawn from our analyses: (1) the order Octopoda and suborders Cirrata, Incirrata, and Oegopsida are monophyletic groups; (2) the family Spirulidae (Ram's horn squids) are the sister taxon to the family Sepiidae (cuttlefishes); (3) the family Octopodidae, as currently defined, is paraphyletic; (4) the superfamily Argonautoidea are basal within the suborder Incirrata; and (5) the benthic octopus genera Benthoctopus and Enteroctopus are sister taxa.