Studies on genetic connectivity are essential for the design of management strategies for coral reef fisheries. In this study we used a mitochondrial DNA marker to investigate population structure of the reef-associated parrotfish, Scarus ghobban, from four countries, Kenya, Mauritius, Seychelles and Tanzania, in the western Indian Ocean. We obtained nucleotide sequences of the mitochondrial control region for 117 individuals. Measures of haplotype diversity were relatively high. Pairwise population differentiation (FST) was low, but not always non-significant. Analysis of molecular variance (AMOVA) showed genetic differentiation between groups, when the data was partitioned into two groups consisting of samples from Mauritius and Tanzania in one group, and samples from Kenya and Seychelles in another group. Direction of gene flow was estimated using a Bayesian approach. Migration was sometimes asymmetric or directional, coinciding with the flow of major oceanic and coastal currents in the region. Mismatch distributions, based on the observed number of differences among haplotype pairs, produced a unimodal distribution, indicative of recent demographic expansion. Phylogenetic analyses revealed three clades without any geographic structure, suggesting recent migration between historically isolated lineages. We reconstructed the historical demography of S. ghobban and examined it in the context of Pleistocene climate stages and changes in relative sea level. Overall, these results showed that populations of S. ghobban are genetically diverse and have relatively high gene flow, with some genetic structuring in the western Indian Ocean.