Marine animals inhabiting the Indian and Pacific oceans have some of the most extensive species ranges in the world, sometimes spanning over half the globe. These Indo-Pacific species present a challenge for study with both geographic scope and sampling density as limiting factors. Here, we augment and aggregate phylogeographic sampling of the iconic blue sea star, Linckia laevigata Linnaeus, 1758, and present one of the most geographically comprehensive genetic studies of any Indo-Pacific species to date, sequencing 392 base pairs of mitochondrial COI from 791 individuals from 38 locations spanning over 14,000 km. We first use a permutation based multiple-regression approach to simultaneously evaluate the relative influence of historical and contemporary gene flow together with putative barriers to dispersal. We then use a discrete diffusion model of phylogeography to infer the historical migration and colonization routes most likely used by L. laevigata across the Indo-Pacific. We show that estimates of genetic structure have a stronger correlation to geographic distances than to “oceanographic” distances from a biophysical model of larval dispersal, reminding us that population genetic estimates of gene flow and genetic structure are often shaped by historical processes. While the diffusion model was equivocal about the location of the mitochondrial most recent common ancestor (MRCA), we show that gene flow has generally proceeded in a step-wise manner across the Indian and Pacific oceans. We do not find support for previously described barriers at the Sunda Shelf and within Cenderwasih Bay. Rather, the strongest genetic disjunction is found to the east of Cenderwasih Bay along northern New Guinea. These results underscore the importance of comprehensive range-wide sampling in marine phylogeography.