The coral reef sea star Linckia laevigata is common on shallow water coral reefs of the Indo-West Pacific. Its large geographic distribution and comprehensive data from previous studies makes it suitable to examine genetic differentiation and connectivity over large geographical scales. Based on partial sequences of the mitochondrial cytochrome oxidase I (COI) gene this study investigates the genetic population structure and connectivity of L. laevigata in the Western Indian Ocean (WIO) and compares it to previous studies in the Indo-Malay-Philippines Archipelago (IMPA). A total of 138 samples were collected from nine locations in the WIO. AMOVA revealed a low but significant ΦST-value of 0.024 for the WIO populations. In the hierarchical AMOVA, the following grouping rejected the hypothesis of panmixia: (1) Kenya (Watamu, Mombasa, Diani) and Tanzanian Island populations (Misali and Jambiani) and (2) the rest of the WIO sites (mainland Tanzania and Madagascar; ΦCT = 0.03). The genetic population structure was stronger and more significant (ΦST = 0.13) in the comparative analysis of WIO and IMPA populations. Three clades were identified in the haplotype network. The strong genetic differentiation (ΦCT = 0.199, P < 0.001) suggests that Indo-West Pacific populations of L. laevigata can be grouped into four biogeographic regions: (1) WIO (2) Eastern Indian Ocean (3) IMPA and (4) Western Pacific. The findings of this study support the existence of a genetic break in the Indo-West Pacific consistent with the effect of lowered sea level during the Pleistocene, which limited gene flow between the Pacific and Indian Ocean.