The first large systematic collection of benthic invertebrate megafauna from the Australian continental margin (depths > 100 m) revealed high species richness and novelty on the south-western continental slope (∼100–1100 m depth; ∼18° S–35° S). A total of 1979 morphologically defined species was discriminated in seven taxa across all samples: Demospongiae, Decapoda, corals (Octocorallia and Antipatharia), Mollusca, Echinodermata, Ascidiacea, and Pycnogonida. Collectively, 59% were estimated to be new or unnamed species. The distribution pattern of megafaunal communities, analysed with a suite of 17 physical covariates, was most influenced at large spatial scales (>100s km) by bottom temperature, oxygen concentration and latitude, whereas at smaller scales (10s of km), seabed type was most influential. Many covariates are driven by the same physical processes and are correlated (e.g. to depth or latitude), thus it is not possible to ascribe causal relationships to fauna distributions. However, their identification highlights the spatial scales that determine the composition of megafaunal communities. Regional-scale transitions in bottom temperature and oxygen concentration are determined by water masses and currents that interact with the south-western margin seabed in different ways depending on location. The nested, smaller-scale heterogeneity of seabed type, classified simply as ‘hard’ or ‘soft’ terrain, differentiates consolidated attachment sites for sessile fauna from sediments suited to mobile and burrowing fauna. Different physical factors affect the distribution of benthic fauna at different scales. Collectively, these patterns of heterogeneity can be represented in a hierarchical framework that consists of biogeographic provinces, biomes, biogeomorphic features, terrains, and finer scales. The Australian government is using a hierarchical approach to identify bioregions for management purposes; a key aim is to ensure that a National Representative System of Marine Protected Areas (NRSMPA) will meet the requirement of comprehensiveness, adequacy and representativeness. Important findings from this study are that the provincial structure of invertebrate megabenthos broadly aligns with the provincial structure derived earlier from the distribution of fishes, but there are differences in the distribution of individual major taxa at both provincial and megahabitat scales. Representative coverage of rarer taxa or narrowly distributed taxa might not be feasible at the same time as ensuring main fauna groups are adequately represented. The hierarchical scales of heterogeneity of the megabenthos in this area, the differences between taxa, and the high proportion of apparently rare species make it clear that it will be as important to manage the area outside the NRSMPA as to manage the NRSMPA itself. Management will be required at different scales that correspond to the multiscale spatial heterogeneity of continental margin fauna.