Background: Despite poor predictive power, syndromic screening is standard of care for diagnosing sexually transmitted infections (STIs) in low-resource, high HIV-burden settings. Predictive models may augment syndromic screening when diagnostic testing is not universally available for screening high-risk patient populations such as adolescents and young adults living with HIV.Setting: Four hundred fifteen adolescents and young adults living with HIV, age 15-24 years, participated from 3 clinical sites in Eswatini, provided urine, sexual and medical history, and completed physical examination.Methods: STI cases were defined by a positive Xpert result for Chlamydia trachomatis, Neisseria gonorrhea, or Trichomonas vaginalis. Features predictive of an STI were selected through Least Absolute Shrinkage and Selection Operator (LASSO) with 5-fold cross validation. Various model strategies were compared with parametric area under the Receiver Operator Curve (AUC) estimation and inferences were made with bootstrapped standard errors.Results: Syndromic screening poorly predicted STIs [AUC 0.640 95% Confidence Interval (95% CI): 0.577 to 0.703]. A model considering 5 predictors (age group, sex, any sexual activity, not always using condoms (either self or partner), a partner who was 25 years or older, and horizontal or unknown mode of HIV acquisition) predicted STIs better than syndromic screening [AUC: 0.829 (95% CI: 0.774 to 0.885)] and was improved when the risk score was supplemented with leukocyte esterase (LE) testing [AUC: 0.883 (95% CI: 0.806 to 0.961)].Conclusions: This simple predictive model, with or without leukocyte esterase testing, could improve STI diagnosis in HIV-positive adolescents and young adults in high burden settings through complementary use with syndromic screening and to guide patient selection for molecular STI diagnostic tests.