With overfishing reducing the abundance of marine predators in multiple marine ecosystems, knowledge of genomic structure and local adaptation may provide valuable information to assist sustainable management. Despite recent technological advances, most studies on sharks have used small sets of neutral markers to describe their genetic structure. We used 5517 nuclear SNPs and a mtDNA gene to characterize patterns of genetic structure and detect signatures of selection in grey reef sharks (Carcharhinus amblyrhynchos). Using samples from Australia, Indonesia and oceanic reefs in the Indian Ocean we established that large oceanic distances represent barriers to gene flow, while genetic differentiation on continental shelves follows an isolation by distance model. In Australia and Indonesia, differentiation at nuclear SNPs was weak, with coral reefs acting as stepping stones maintaining connectivity across large distances. Differentiation of mtDNA was stronger, and more pronounced in females, suggesting sex biased dispersal. Four independent tests identified a set of loci putatively under selection, indicating that grey reef sharks in eastern Australia are likely under different selective pressures to those in Western Australia and Indonesia. Genetic distances averaged across all loci were uncorrelated with genetic distances calculated from outlier loci, supporting the conclusion that different processes underpin genetic divergence in these two data sets. This pattern of heterogeneous genomic differentiation, suggestive of local adaptation, has implications for the conservation of grey reef sharks; furthermore, it highlights that marine species showing little genetic differentiation at neutral loci may exhibit patterns of cryptic genetic structure driven by local selection.