Grey reef sharks (Carcharhinus amblyrhynchos) can be one of the numerically dominant high order predators on pristine coral reefs, yet their numbers have declined even in the highly regulated Australian Great Barrier Reef (GBR) Marine Park. Knowledge of both large scale and fine scale genetic connectivity of grey reef sharks is essential for their effective management, but no genetic data are yet available. We investigated grey reef shark genetic structure in the GBR across a 1200 km latitudinal gradient, comparing empirical data with models simulating different levels of migration. The empirical data did not reveal any genetic structuring along the entire latitudinal gradient sampled, suggesting regular widespread dispersal and gene flow of the species throughout most of the GBR. Our simulated datasets indicate that even with substantial migrations (up to 25% of individuals migrating between neighboring reefs) both large scale genetic structure and genotypic spatial autocorrelation at the reef scale were maintained. We suggest that present migration rates therefore exceed this level. These findings have important implications regarding the effectiveness of networks of spatially discontinuous Marine Protected Areas to protect reef sharks.