Among 865 adults with early syphilis considered for a multicenter treatment trial, 234 (27%) were excluded before enrollment because of bacterial sexually transmitted infection coinfection. Coinfection with Neisseria gonorrhoeae (29%), Chlamydia trachomatis (22%), or both (23%) was common. Study findings highlight the need for comprehensive bacterial sexually transmitted infection screening in patients with syphilis.