Substance misuse is a significant issue in Australia, and a large proportion of individuals with substance misuse disorders have co-existing mental health disorders. There is evidence that Indigenous Australians are more likely than non-Indigenous Australians to experience the adverse effects of alcohol consumption, and that mental health disorders are more prevalent in Indigenous communities than non-Indigenous communities. Indigenous Australians currently do not access mental health and substance abuse services at a level which is consistent with their level of need, and this is largely due to inconsistent or insufficient culturally respectful mental health services. This paper provides a review of relevant literature, which indicates an increasing need for mental health and substance abuse services that are sensitive to the needs of Indigenous Australians, and discusses engagement challenges and what is needed to increase engagement and improve outcomes for these clients. Future research should aim to identify which approaches to mental health and substance abuse service provision are associated with better outcomes for Indigenous clients, and ways of increasing the cultural respectfulness of these services.