Octopus cyanea (Gray, 1849), abundant in the South-West Indian Ocean (SWIO), constitutes a vital resource for both subsistence and commercial fisheries. However, despite this socioeconomic importance, and recent indications of overfishing, little is known about the population structure of O. cyanea in the region. To inform sustainable management strategies, this study assessed the spatio-temporal population structure and genetic variability of O. cyanea at 20 sites in the SWIO (Kenya, Tanzania, Mozambique, Madagascar, Mauritius, Rodrigues, and the Seychelle Islands) by complementary analysis of mitochondrial DNA (mtDNA) noncoding region (NCR) sequences and microsatellite markers. MtDNA analysis revealed a shallow phylogeny across the region, with demographic tests suggesting historic population fluctuations that could be linked to glacial cycles. Contrary to expectations, NCR variation was comparable to other mtDNA regions, indicating that the NCR is not a hypervariable region. Both nuclear and mtDNA marker types revealed a lack of genetic structure compatible with high gene flow throughout the region. As adults are sedentary, this gene flow likely reflects connectivity by paralarval dispersal. All samples reported heterozygote deficits, which, given the overall absence of structure, likely reflect ephemeral larval recruitment variability. Levels of mtDNA and nuclear variability were similar at all locations and congruent with those previously reported for harvested Octopodidae, implying resilience to genetic erosion by drift, providing current stock sizes are maintained. However, as O. cyanea stocks in the SWIO represent a single, highly connected population, fisheries may benefit from additional management measures, such as rotational closures aligned with paralarval ecology and spanning geopolitical boundaries.