Background: The aim of this study was to study ecological correlations between age-adjusted all-cause mortality rates in Australian statistical divisions and (1) the proportion of residents that self-identify as Indigenous, (2) remoteness, and (3) socio-economic deprivation. Methods: All-cause mortality rates for 57 statistical divisions were calculated and directly standardized to the 1997 Australian population in 5-year age groups using Australian Bureau of Statistics (ABS) data. The proportion of residents who self-identified as Indigenous was obtained from the 1996 Census. Remoteness was measured using ARIA (Accessibility and Remoteness Index for Australia) values. Socio-economic deprivation was measured using SEIFA (Socio-Economic Index for Australia) values from the ABS. Results: Age-standardized all-cause mortality varies two-fold from 5.7 to 11.3 per 1000 across Australian statistical divisions. Strongest correlation was between Indigenous status and mortality (r = 0.69, p < 0.001). Correlation between remoteness and mortality was modest (r = 0.39, p = 0.002) as was correlation between socio-economic deprivation and mortality (r = -0.42, p = 0.001). Excluding the three divisions with the highest mortality, a multiple regression model using the logarithm of the adjusted mortality rate as the dependent variable showed that the partial correlation (and hence proportion of the variance explained) for Indigenous status was 0.03 (9 per cent; p = 0.03), for SEIFA score was -0.17 (3 per cent; p = 0.22); and for remoteness was -0.22 (5 per cent; p = 0.13). Collectively, the three variables studied explain 13 per cent of the variability in mortality. Conclusions: Ecological correlation exists between all-cause mortality, Indigenous status, remoteness and disadvantage across Australia. The strongest correlation is with Indigenous status, and correlation with all three characteristics is weak when the three statistical divisions with the highest mortality rates are excluded. Intervention targeted at these three statistical divisions could reduce much of the variability in mortality in Australia.