Background: Australia has set a national target of ending HIV by 2020, achieving this will require the inclusion of priority populations (eg, Indigenous Australians) in strategies to reach elimination. To assist in evaluating the target of elimination, we analysed HIV notification data for Indigenous and non-Indigenous Australians. Methods: Using the National HIV Registry at The Kirby Institute at UNSW, Sydney, NSW, Australia, we collated and analysed annual HIV notification data for 1996–2015. Patients who were not born in Australia were excluded. We calculated the rates of HIV diagnoses with annual trends in notification rates for Indigenous versus non-Indigenous Australians by demographic characteristics, exposure categories, and stage of HIV at diagnosis. For missing data, assumptions were made and verified through sensitivity analyses. Annual rate ratio (RR) and 4 year summary rate ratio (SRR) trends were calculated to determine patterns of HIV diagnosis in the two populations. Findings: Between Jan 1, 1996, and Dec 31, 2015, 11 492 people born in Australia were reported with a diagnosis of HIV, of whom 461 (4%) were recorded as Indigenous Australians and we classified the remaining 11 031 (96%) as non-Indigenous Australians. For exposure to HIV, among Indigenous Australians a higher proportion of diagnoses occurred among women, and through injecting drug use and heterosexual sex than among non-Indigenous Australians (p<0·0001). Among Indigenous Australians, we found a significantly higher SRR of HIV diagnoses among men in the period 2012–15 than in previous periods (SRR 1·53, 95% CI 1·28–1·83; p<0·0001), and significantly higher diagnosis among Indigenous women (4·92, 4·02–6·02; p<0·0001) for the entire study period than among non-Indigenous women. Concurrently, a decrease in HIV diagnoses of 1% per annum (RR 0·99, 95% CI 0·98–0·99; p<0·0001) across the study period was seen among non-Indigenous people. Indigenous Australians were more likely to be diagnosed at an advanced stage of HIV infection than non-Indigenous Australians (20·8% vs 15·1%; p=0·0088). Interpretation: Greater efforts should be made to include Indigenous people in prevention strategies, particularly newer biomedical interventions, such as scale up of pre-exposure prophylaxis and treatment as prevention initiatives in Australia. More involvement of Indigenous Australians in these approaches is also required to prevent widening of the gap in HIV diagnosis rates between non-Indigenous and Indigenous Australians. Funding: None.