The cephalopod genus Nautilus is considered a “living fossil” with a contested number of extant and extinct species, and a benthic lifestyle that limits movement of animals between isolated seamounts and landmasses in the Indo-Pacific. Nautiluses are fished for their shells, most heavily in the Philippines, and these fisheries have little monitoring or regulation. Here, we evaluate the hypothesis that multiple species of Nautilus (e.g., N. belauensis, N. repertus and N. stenomphalus) are in fact one species with a diverse phenotypic and geologic range. Using mitochondrial markers, we show that nautiluses from the Philippines, eastern Australia (Great Barrier Reef), Vanuatu, American Samoa, and Fiji fall into distinct geographical clades. For phylogenetic analysis of species complexes across the range of nautilus, we included sequences of Nautilus pompilius and other Nautilus species from GenBank from localities sampled in this study and others. We found that specimens from Western Australia cluster with samples from the Philippines, suggesting that interbreeding may be occurring between those locations, or that there is limited genetic drift due to large effective population sizes. Intriguingly, our data also show that nautilus identified in other studies as N. belauensis, N. stenomphalus, or N. repertus are likely N. pompilius displaying a diversity of morphological characters, suggesting that there is significant phenotypic plasticity within N. pompilius.