Large vagile mammals typically exhibit little genetic structuring across their range, particularly when their habitat is essentially continuous. We investigated the population genetic structure of a large vagile Australian macropodid, Macropus fuliginosus, which is continuously distributed across most of southern Australia, using nine highly polymorphic nuclear microsatellite loci. Five distinct genetic units were identified across the range, four on the mainland and one on Kangaroo Island. In addition to the predicted historic Nullarbor Plain Barrier, two unexpected mainland barriers to gene flow were identified. Both were associated with landscape discontinuities (Swan River, Flinders Ranges), which appear within the dispersal capabilities of M. fuliginosus. Typical of large vagile mammals, M. fuliginosus displays high genetic diversity (with the exception of an insular population) and weak genetic structuring (within genetic units). However, the expansion of M. fuliginosus from southwestern Australia during the Pleistocene has resulted in significantly reduced genetic diversity in eastern populations. No significant sex-biased dispersal was detected, although differences in habitat, densities and climatic conditions between the eastern and western regions of the range appear to influence dispersal with the effects of isolation by distance only evident in the west. These results suggest that the biogeography of southern Australia is more complex than previously thought and reveal that seemingly minor landscape features can significantly impact genetic structuring in large vagile mammals.