The northwestern Indian Ocean harbors a number of larger marine vertebrate taxa that warrant the investigation of genetic population structure given remarkable spatial heterogeneity in biological characteristics such as distribution, behavior, and morphology. Here, we investigate the genetic population structure of four commercially exploited shark species with different biological characteristics (Carcharhinus limbatus, Carcharhinus sorrah, Rhizoprionodon acutus, and Sphyrna lewini) between the Red Sea and all other water bodies surrounding the Arabian Peninsula. To assess intraspecific patterns of connectivity, we constructed statistical parsimony networks among haplotypes and estimated (1) population structure; and (2) time of most recent population expansion, based on mitochondrial control region DNA and a total of 20 microsatellites. Our analysis indicates that, even in smaller, less vagile shark species, there are no contemporary barriers to gene flow across the study region, while historical events, for example, Pleistocene glacial cycles, may have affected connectivity in C. sorrah and R. acutus. A parsimony network analysis provided evidence that Arabian S. lewini may represent a population segment that is distinct from other known stocks in the Indian Ocean, raising a new layer of conservation concern. Our results call for urgent regional cooperation to ensure the sustainable exploitation of sharks in the Arabian region.