The biogeography of the deep-sea benthic fauna is uncertain due to the vast size and incomplete exploration of these environments. While shallow water assemblages are differentiated into tropical, temperate and polar faunas, it is unknown whether these units extend to lower depths. Here we use model-based statistics to analyse megafaunal benthic samples along a 2,300 km transect off the eastern Australian continental margin. We show that a temperate-tropical transition between 33-31˚S occurs at both lower bathyal (~2500 m) and abyssal (~4000 m) depths. This transition occurs despite almost uniform temperature, salinity and dissolved oxygen concentrations occurring across latitudes at these depths. Conversely, the patterns are consistent with the flux of organic matter to the seafloor, which varies from being relatively high in the productive temperate off SE Australia to low levels in more-oligotrophic tropical waters. Biodiversity is not uniform across the deep-sea and regional-scale heterogeneity needs to be incorporated into marine park designs.