Background: Approximately 15% of HIV-infected men who have sex with men (MSM) engaged in HIV primary care have been diagnosed as having a sexually transmitted infection (STI) in the past year, yet STI testing frequency remains low. Methods: We sought to quantify STI testing frequencies at a large, urban HIV care clinic, and to identify patient- and provider-related barriers to increased STI testing. We extracted laboratory data in aggregate from the electronic medical record to calculate STI testing frequencies (defined as the number of HIV-infectedMSM engaged in care who were tested at least once over an 18-month period divided by the number of MSM engaged in care). We created anonymous surveys of patients and providers to elicit barriers. Results: Extragenital gonorrhea and chlamydia testing was low (29%- 32%), but the frequency of syphilis testing was higher (72%). Patients frequently reported high-risk behaviors, including drug use (16.4%) and recent bacterial STI (25.5%), as well as substantial rates of recent testing (>60% in prior 6 months).Most (72%) reported testing for STI in HIV primary care, but one-third went elsewhere for "easier" (42%), anonymous (21%), or more frequent (16%) testing. HIV primary care providers lacked testing and treatment knowledge (25%-32%) and cited lack of time (68%), discomfort with sexual history taking and genital examination (21%), and patient reluctance (39%) as barriers to increased STI testing. Conclusion: Sexually transmitted infection testing in HIV care remains unacceptably low. Enhanced education of providers, along with strategies to decrease provider time and increase patient ease and frequency of STI testing, is needed.