Objectives: To assess notification trends for chlamydia and gonorrhoea infections in Indigenous Australians compared with non-Indigenous Australians in 2000–2009. Design and setting: We assessed trends in national notification rates using univariate Poisson regression and summary rate ratios. Main outcome measures: Crude notification rates and summary rate ratios, by Indigenous status, sex, age and area of residence. Results: Over the 10-year period studied, chlamydia notification rates per 100 000 increased by 80% from 1383 in 2000 to 2494 in 2009 among Indigenous people, and by 335% from 51 in 2000 to 222 in 2009 among non-Indigenous people. The Indigenous versus non-Indigenous summary rate ratio was 23.92 (95% CI, 23.65–24.19; P < 0.001). Gonorrhoea notification rates per 100 000 increased by 22% from 1347 in 2000 to 1643 in 2009 among Indigenous people, and by 70% from 10 in 2000 to 17 in 2009 among non-Indigenous people. The gonorrhoea summary notification rate ratio in Indigenous compared with non-Indigenous people was 173.78 (95% CI, 170.81– 176.80; P < 0.001). In Indigenous people, the highest chlamydia and gonorrhoea notification rates were in women, 15–19-year-olds, and those living in remote areas. Conclusions: Chlamydia and gonorrhoea notification rates have increased in both populations but were higher among Indigenous people. Our findings highlight the need for targeted prevention programs for young people, especially Indigenous Australians residing in remote areas.