Against the backdrop of rising rates of sexually transmitted infections (STIs), the aim of this article is to analyze the prevalence of STI co-infections among individuals who learned of their HIV-positive status between 2012 and 2016. Since 2012, mandatory HIV reporting has collected data on four bacterial STIs among adults aged 15 and older: syphilis, gonorrhea, and Chlamydia trachomatis infections, including lymphogranuloma venereum (LGV). These STIs must be reported if they were diagnosed concurrently with the discovery of HIV seropositivity or within the 12 months preceding that discovery (defined as STI/HIV co-infections). Over the 2012–2016 period, information on a potential STI was available for 12 out of 588 HIV-positive diagnoses in adults, representing 52% of diagnoses. The overall prevalence of STI/HIV co-infections was 14.6%, but was higher among men who have sex with men (MSM) (26.5%) than among heterosexuals (5.2%) or people who inject drugs (7.2%). The prevalence of co-infections increased significantly over time, rising from 12.7% in 2012 to 17.5% in 2016. The increase was also significant among MSM (from 22.1% to 30.9%). Syphilis was the most frequently diagnosed STI at the time of HIV seropositivity diagnosis or within the preceding 12 months, particularly among MSM. Overall, STI/HIV co-infections have increased since 2012 and affect nearly one-third of MSM who learned of their HIV status in 2016. These results underscore the importance of combining HIV testing with testing for other STIs, as recommended in France. In the current context of diversified HIV prevention, where condoms are no longer the sole prevention strategy, it is particularly important to conduct regular STI testing to ensure prompt treatment for patients and their partners.