Deep reef assemblages in south-eastern Australia are poorly described, and have been surveyed by only a few studies conducted over small spatial scales. Here, we characterise the composition of deep(similar to 30-90 m depth) sessile invertebrate communities from sub-tropical (27 degrees S) to temperate eastern Australia (43 degrees S). We estimated the cover of 51 preselected invertebrate types from over 1700 seafloor images collected by an autonomous underwater vehicle from >105 km of transects across the study region. Seafloor images were assessed using 3 alternative schemes reflecting different resolution of benthic invertebrate groupings, including the broadlevel Collaborative and Automated Tools for Analysis of Marine Imagery project ('CATAMI') classification recently developed as a generic scoring approach for seafloor imagery. Ordination using canonical analysis of principal coordinates indicated a clear latitudinal gradient in benthic community composition and, particularly when based on individual morphotypes, 3 distinct community types (sub-tropical, warm temperate and cool temperate). Changes in community structure mostly correlated with primary productivity and the temperature climatology, while local-scale variability in community composition was most related to depth. Along with the gradual shift in deep reef community composition across latitudes, region-specific sessile invertebrates might serve as useful indicators of change in these deep benthic communities under future changes in ocean climate in the region, which has been identified as a global hotspot for ocean warming. Our methodological approach has general applicability for large-scale surveying and monitoring of benthic communities using underwater imagery.