Despite extensive revisions over recent decades, the taxonomy of benthic octopuses (Family Octopodidae) remains in a considerable flux. Among groups of unresolved status is a species complex of morphologically similar shallow-water octopods from subtropical Australasia, including: Allopatric populations of Octopus tetricus on the eastern and western coasts of Australia, of which the Western Australian form is speculated to be a distinct or sub-species; and Octopus gibbsi from New Zealand, a proposed synonym of Australian forms. This study employed a combination of molecular and morphological techniques to resolve the taxonomic status of the 'tetricus complex'. Phylogenetic analyses (based on five mitochondrial genes: 12S rRNA, 16S rRNA, COI, COIII and Cytb) and Generalised Mixed Yule Coalescent (GMYC) analysis (based on COI, COIII and Cytb) distinguished eastern and Western Australian O. tetricus as distinct species, while O. gibbsi was found to be synonymous with the east Australian form (BS = >97, PP = 1; GMYC p = 0.01). Discrete morphological differences in mature male octopuses (based on sixteen morphological traits) provided further evidence of cryptic speciation between east (including New Zealand) and west coast populations; although females proved less useful in morphological distinction among members of the tetricus complex. In addition, phylogenetic analyses suggested populations of octopuses currently treated under the name Octopus vulgaris are paraphyletic; providing evidence of cryptic speciation among global populations of O. vulgaris, the most commercially valuable octopus species worldwide.