Invasive predators are identified as an important threatening process implicated in native species decline and extinction in Australia. This study aimed at developing our understanding of landscape-level spatial patterns in the red fox diet. We established prey importance based on dietary composition of red fox scats, and related this information to landscape structure. The relationship between scat composition and the frequency of detection and spatial patterns of occurrence of small mammals based on survey data from the same region was also evaluated using ordination analyses. We found that native vertebrates, dominated by Sminthopsinae, were the most important prey. However, Mus musculus were detected significantly more than Sminthopsinae across the region. Sminthopsinae were detected most frequently in traps in grazing landscapes; however, red fox scats from grazing landscapes were dominated by invertebrates. We propose these patterns may be partially driven by M. musculus abundance attracting predation pressure to the landscape and Sminthopsinae exhibiting prey naivety resulting in their disproportional representation in red fox scats.