Territorial group size in Australian magpies (Gymnorhina tibicen) ranges from monogamous pairs to groups of more than 20 individuals. It has been hypothesized that large territorial groups result from the retention of juveniles after a breeding effort. If this is true, local populations consisting of large groups are likely to exhibit the most genetic structure, because over time similar genotypes will tend to be confined to limited areas if juveniles are predominantly philopatric. The objective of the present study was to test this hypothesis using allozyme and mitochondrial DNA data to provide indirect estimates of regional gene flow (derived from hierarchical population subdivision analyses). These data were used in combination with estimates of group size to infer patterns of dispersal among magpie populations across mainland Australia. Territorial groups were significantly larger in the south-west compared to three eastern regions. Although inferred levels of gene flow were substantial for all four regions, a striking pattern emerged from both sets of genetic data: more differentiation was evident among populations in the south-western region than in any eastern region. We conclude that levels of juvenile dispersal influence group size in G. tibicen, because in the south-western region where groups were largest, populations were most genetically differentiated. Our results suggest that contrasting population genetic structures may develop within a single species as a result of differences in social system.