Multiple species of large octopus are known from the north Pacific waters around Japan, however only one large species is known in the Gulf of Alaska (the giant Pacific octopus, Enteroctopus dofleini). Current taxonomy of E. dofleini is based on geographic and morphological characteristics, although with advances in genetic technology that is changing. Here, we used two mitochondrial genes (cytochrome b and cytochrome oxidase I), three nuclear genes (rhodopsin, octopine dehydrogenase, and paired-box 6), and 18 microsatellite loci for phylogeographic and phylogenetic analyses of octopuses collected from across southcentral and the eastern Aleutian Islands (Dutch Harbor), Alaska. Our results suggest the presence of a cryptic Enteroctopus species that is allied to, but distinguished from E. dofleini in Prince William Sound, Alaska. Existence of an undescribed and previously unrecognized taxon raises important questions about the taxonomy of octopus in southcentral Alaska waters.