Most population genetics studies of rock-wallabies conducted to date have examined remnant colonies of threatened species inhabiting southern Australia. In this study we examined the natural pattern of contemporary and long-term gene flow among colonies of the widespread and abundant short-eared rock-wallaby, Petrogale brachyotis, in the relatively unmodified landscapes of Australia’s tropical north. We sampled 105 wallabies from seven colonies 1.2 km to 250 km apart. Mitochondrial DNA (mtDNA) control region sequence analysis was conducted on samples from all colonies and microsatellite analysis (10 loci) on samples from the three largest colonies. The microsatellite data revealed no evidence of inbreeding within colonies, but higher levels of genetic diversity were found in the Kakadu National Park population compared with the smaller, more isolated colonies at Litchfield National Park. Both the mtDNA and microsatellite results showed that populations of P. brachyotis are naturally highly structured even within this relatively intact landscape, with only limited contemporary and long-term gene flow between colonies more than 1.2 km apart. Nine mtDNA control region haplotypes were identified within the seven colonies. There were unusually high levels of sequence divergence (up to 6.9%) within colonies at Litchfield NP. This divergence suggests that multiple taxa may exist within what is currently recognised as P. brachyotis. Alternatively, if current taxonomy is correct, the high levels of divergence raise the possibility of ancestral isolation and divergence of populations in allopatry with subsequent admixture at a secondary contact zone. The possibility that these unusually divergent haplotypes result from introgressive interspecific hybridisation with the sympatric P. concinna appears unlikely.