Connectivity underpins the persistence and recovery of marine ecosystems. The Great Barrier Reef (GBR) is the world's largest coral reef ecosystem and managed by an extensive network of no-take zones; however, information about connectivity was not available to optimize the network's configuration. We use multivariate analyses, Bayesian clustering algorithms and assignment tests of the largest population genetic data set for any organism on the GBR to date (Acropora tenuis, >2500 colonies; >50 reefs, genotyped for ten microsatellite loci) to demonstrate highly congruent patterns of connectivity between this common broadcast spawning reef-building coral and its congener Acropora millepora (~950 colonies; 20 reefs, genotyped for 12 microsatellite loci). For both species, there is a genetic divide at around 19°S latitude, most probably reflecting allopatric differentiation during the Pleistocene. GBR reefs north of 19°S are essentially panmictic whereas southern reefs are genetically distinct with higher levels of genetic diversity and population structure, most notably genetic subdivision between inshore and offshore reefs south of 19°S. These broadly congruent patterns of higher genetic diversities found on southern GBR reefs most likely represent the accumulation of alleles via the southward flowing East Australia Current. In addition, signatures of genetic admixture between the Coral Sea and outer-shelf reefs in the northern, central and southern GBR provide evidence of recent gene flow. Our connectivity results are consistent with predictions from recently published larval dispersal models for broadcast spawning corals on the GBR, thereby providing robust connectivity information about the dominant reef-building genus Acropora for coral reef managers.