Background Earlier age at sexual debut is associated with drug and alcohol use, risky sexual behaviours and sexually transmissible infections (STI). Methods: In the present study, 2320 young Indigenous Australians were surveyed. Results: Most study participants had sex for the first time when they were 14 years or younger (79% and 67% for males and females respectively). More than 80% of participants were categorised as being in the high-risk category for the combined sexual risk factors (i.e. not using condoms, drunk or high at last sexual act, or three or more sexual partners in the past year). There was a linear decreasing trend between the proportion of males and females who had less than high school education and age at first sex (Ptrend < 0.001). Compared with the highest quintile of age at first sexual debut (≥18 years), those in the bottom quintile (<15 years) were less likely to have completed high school (63% vs 32% respectively for males; 68% vs 26% respectively for females; Ptrend < 0.001 for both). Conclusions: The findings of the present study suggest that sex education and STI prevention should start early when targeting Indigenous young people, with age-appropriate messages. Sex education should be comprehensive and address individual risk behaviours, sexual agency and societal vulnerability to not only delay sexual debut, but also to emphasise the importance of STI prevention through condom use, which clearly already works to a certain extent with this group.