The sea cucumber, Holothuria nobilis, has a long-lived planktotrophic larvae, and previous allozyme surveys have suggested that high dispersal is realized. In contrast, recent ecological studies indicate that dispersal is low. To reconcile these data, and to investigate the evolution of this Indo-Pacific species, we screened geographical variation in 559 bp of a mitochondrial gene (COI) in 360 samples from the Australasian region and La Réunion. Sequences from La Réunion differed by > 7% from others and may constitute another species. Haplotype diversity in other samples was high (0.942, SD = 0.007), but haplotypes were closely related (mean nucleotide diversity: 0.0075, SD = 0.0041). AMOVA, pairwise FST values and exact tests did not detect significant population structure. Nested clade analysis showed that one of two main clades was over-represented in west Australia, whereas the other was more common in the northern Great Barrier Reef. Isolation-by-distance was identified as the main determinant of population structure at several clade levels. Contiguous range expansion was inferred for evolutionary older clade levels and this may correspond to a late Pleistocene (88 000-193 000 years ago) population expansion inferred from haplotype mismatch distributions. Thus, the population genetic structures detected are likely to be formed prior to the last ice age, with some indications for high dispersal on shorter time scales.