Background: Indigenous Australians are known to be at greater risk of morbidity and mortality from mental health related conditions, but most available data relate to the use of mental health services, and little is known about other aspects of social and emotional wellbeing. Using the first available nationally representative data, we examined the prevalence and patterning of psychological distress among Indigenous Australian adults and compared these with corresponding data from the non-Indigenous population. Methods. The analysis used weighted data on psychological distress, as measured by a modified Kessler Psychological Distress score (K5), and a range of socio-demographic measures for 5,417 Indigenous and 15,432 non-Indigenous adults aged 18-64 years from two nationally representative surveys. Very high psychological distress (VHPD) was defined as a K5 score ≥15 (possible range = 5-25). Results: Indigenous adults were about three times more likely than non-Indigenous adults to be classified with VHPD: 14.5% (95% confidence interval (CI) 12.9-16.0%) versus 5.5% (95% CI 5.0-5.9%). After adjusting for age, most socio-demographic variables were significantly associated with VHPD in both populations, although the relative odds were generally larger among non-Indigenous people. Indigenous people in remote areas had a lower prevalence of VHPD than their non-remote counterparts, and only marital status, main language, and food insecurity were significantly associated with VHPD in remote areas. Conclusions: Higher absolute levels of VHPD combined with smaller socio-demographic gradients in the Indigenous population suggest the importance of risk factors such as interpersonal racism, marginalization and dispossession, chronic stress and exposure to violence that are experienced by Indigenous Australians with common and/or cross-cutting effects across the socioeconomic spectrum. The lower prevalence of VHPD and lack of association with many socio-demographic variables in remote areas suggests either that the instrument may be less valid for Indigenous people living in remote areas or that living in an Indigenous majority environment (such as exists in most remote communities) may mitigate the risk of psychological distress to some degree.