Many species of the genus Octopus are important resources for fisheries worldwide. Its approximately 200 species show a strong similarity in structural morphology and a wide diversity in skin coloration and patterning, behaviour and life strategies that have hampered the study of phylogenetic relationships. We used a Bayesian approach to estimate as yet unknown phylogenetic relationships among O. tehuelchus from the southwestern Atlantic, new specimens of O. mimus (Chile and Peru) and other Octopus species, and used Bayes factors to test phylogenetic hypotheses. O. tehuelchus was more closely related to the genera Callistoctopus, Grimpella and Macroctopus than to Octopus, and therefore its generic placement may need a revision. O. vulgaris specimens from Costa Rica (Pacific Ocean) and O. oculifer grouped with O. mimus. Bayes factors showed positive evidence in favor of this grouping and therefore these individuals could have been misidentified, being in fact O. mimus. O. vulgaris specimens from the Costa Rican Caribbean were more related to O. mimus than to other O. vulgaris and could represent a cryptic species. The remaining O. vulgaris clustered with O. tetricus. Bayes factors found strong evidence against the monophyly of O. vulgaris as currently defined, giving statistical support to the monophyly of an O. vulgaris s. str. + O. tetricus group proposed previously by other authors.