Identifying and targeting those at greatest risk will likely play a significant role in developing the most efficient and cost-effective sexually transmissible infections (STI) prevention programs. We aimed to develop a risk prediction algorithm to identify those who are at increased risk of STI. A cohort (N = 2320) of young sexually active Aboriginal and Torres Strait Islander people (hereafter referred to as Aboriginal people) were included in this study. The primary outcomes were self-reported high-risk sexual behaviors and past STI diagnosis. In developing a risk algorithm, our study population was randomly assigned to either a development (67%) or an internal validation data set (33%). Logistic regression models were used to create a risk prediction algorithm from the development data set for males and females separately. In the risk prediction models, older age, methamphetamine, ecstasy, and cannabis use, and frequent alcohol intake were all consistently associated with high-risk sexual behaviors as well as with a past STI diagnosis; identifying as gay/bisexual was one of the strongest factors among males. Those who had never tested for STIs, 52% (males) and 66% (females), had a risk score >15, and prevalence of undiagnosed STI was estimated between 30 and 40%. Since universal STI screening is not cost-effective, nor practical in many settings, targeted screening strategies remain a crucial and effective approach to managing STIs among young Aboriginal people. Risk prediction tools such as the one developed in this study may help in prioritizing screening for STIs among those most at risk.