Understanding the distribution of genetic diversity in exploited species is fundamental to successful conservation. Genetic structure and the degree of gene flow among populations must be assessed to design appropriate strategies to prevent the loss of distinct populations. The cephalopod Nautilus pompilius is fished unsustainably in the Philippines for the ornamental shell trade and has limited legislative protection, despite the species' recent dramatic decline in the region. Here, we use 14 microsatellite markers to evaluate the population structure of N. pompilius around Australia and the Philippines. Despite their relative geographical proximity, Great Barrier Reef individuals are genetically isolated from Osprey Reef and Shark Reef in the Coral Sea (FST  = 0.312, 0.229, respectively). Conversely, despite the larger geographical distances between the Philippines and west Australian reefs, samples display a small degree of genetic structure (FST  = 0.015). Demographic scenarios modelled using approximate Bayesian computation analysis indicate that this limited divergence is not due to contemporary gene flow between the Philippines and west Australia. Instead, present-day genetic similarity can be explained by very limited genetic drift that has occurred due to large average effective population sizes that persisted at both locations following their separation. The lack of connectivity among populations suggests that immigrants from west Australia would not facilitate natural recolonization if Philippine populations were fished to extinction. These data help to rectify the paucity of information on the species' biology currently inhibiting their conservation classification. Understanding population structure can allow us to facilitate sustainable harvesting, thereby preserving the diversity of genetically distinct stocks.