Populations of many Mediterranean marine species show a strong phylogeographic structure, but the knowledge available for native seaweeds is limited. We investigated the genetic diversity of the green alga Halimeda tuna based on two plastid markers (tufA gene and a newly developed amplicon spanning five ribosomal protein genes and intergenic spacers, the rpl2‐rpl14 region). The tufA sequences showed that Mediterranean H. tuna represents a single, well‐defined species. The rpl2‐rpl14 results highlighted a genetic separation between western and eastern Mediterranean populations; specimens collected from widely scattered locations in the Adriatic/Ionian region shared a haplotype unique to this region, and formed a group separated from all western Mediterranean regions. Specimens from Sardinia also formed a unique haplotype. Within the western Mediterranean basin, a gradual shift in the frequency of haplotypes was apparent along a West‐East gradient. Our results represent the first clear evidence of an East‐West genetic cleavage in a native Mediterranean macroalga and offer an interesting perspective for further research into fine‐scale seaweed population structure in the NW Mediterranean Sea.