Phylogenetic relationships among 36 species of major coleoid cephalopods from Japanese waters were studied using partial sequences of three mitochondrial genes, 16S rDNA, 12S rDNA, and cytochrome c oxidase subunit I gene. Octopoda and Decapoda were monophylic groups. Within Sepioidea, Sepiadariidae and Sepiolidae were not closely related to Sepiidae, but rather related to Teuthoidea. Sepiidae with a distinct calcareous shell formed a single cluster. Myopsida was closely related to Oegopsida. Within Octopoda, Opisthoteuthis depressa and Argonauta argo diverged earlier than Octopodiidae. The common octopuses in Japanese waters were separated into three clusters. The first cluster occupied a basal position, and includes large-sized octopuses, such as Enteroctopus dofleini and Octopus (Paroctopus) conispadiceus from the continental shelf and upper slope. The second cluster consisted of long-armed octopuses, such as O. ornatus, O. minor, and O. sasakii. The third cluster contained small- to medium-sized octopus, such as Amphioctopus fangsiao, A. areolatus, O. cyaneus, and O. vulgaris, in which several species possess ocelli on the web. The second cluster formed the sister group to the third cluster.