Phylogeographic structure was investigated in the blue-spotted maskray, Neotrygon kuhlii, focusing on the Coral Triangle region. We used as genetic marker a 519-bp fragment of the cytochrome c-oxidase subunit I (COI) gene, sequenced in a total of 147 individuals from 26 sampling locations. The parsimony network of COI haplotypes was split into seven distinct clades within the Coral Triangle region. Different clades had exclusive but contiguous geographic distributions, indicating parapatric-like phylogeographic structure. Strong genetic differences were also inferred between local populations within a clade, where reciprocal monophyly between geographically adjacent samples was observed on several instances. Nearly 25% of the total molecular variance could be ascribed to differences between geographic samples within a clade, whereas interclade variation accounted for >65% of the total variance. The strong phylogeographic structure observed within a clade can be explained by either sedentarity or female philopatry. We interpret the parapatric distribution of clades as the joint result of 1) expansion from refuge populations at times of low sea level, and 2) possible enhanced competition between individuals from different clades, or assortative mating, or hybrid zones, along lines of secondary contact. The parapatric-like structure uncovered in the present study parallels regional differences at nuclear marker loci, thus pointing to incipient speciation within Coral Triangle N. kuhlii.