Background: HIV and bacterial sexually transmissible infection (STI) notifications among men who have sex with men (MSM) have increased in Australia and many other countries. The relationship between HIV infection and other STIs has been demonstrated previously. However, the relationship between the cumulative history of STIs and subsequent HIV infection remains largely unexplored and limits our understanding of the mechanisms underpinning the elevated HIV risk. Methods: Data from HIV-negative MSM who attended high-HIV caseload primary care clinics in Melbourne, Australia, from 2007 to 2014 with 2 or more HIV and STI tests were included. Controlling for sexual behaviors self-reported at clinic visits, discrete time survival analyses using generalized linear modeling estimated the effect of an STI at the prior test event and the cumulative history of STIs (none, 1, 2, or more [repeated]) on risk of HIV infection. Results: A total of 8941 MSM met the study criteria; 227 (2.5%) were diagnosed with HIV over the follow-up period. Adjusting for sexual behaviors, a cumulative history of repeated rectal gonorrhea infections (adjusted hazard ratio [aHR], 6.27; 95% confidence interval [CI], 2.68-14.50) and a single rectal gonorrhea infection (aHR, 2.09; 95% CI, 1.15-3.79) were associated with increased HIV infection risk. Conclusions: Repeated and single rectal gonorrhea infections were independently associated with increased HIV infection risk. These findings suggest that MSM with any history of rectal gonorrhea, particularly repeat rectal gonorrhea, represent a group for whom preventive interventions for HIV should be emphasized.