Methicillin-resistant Staphylococcus aureus (MRSA) infections are an important cause of morbidity, especially among human immunodeficiency virus (HIV)-infected persons. Since an increasing number of MRSA skin and soft tissue infections involve the perigenital areas, some have suggested that these infections may be sexually transmitted. We performed a cross-sectional study among HIV-infected adults from 4 geographically diverse United States military HIV clinics to determine the prevalence of and the factors (including sexual practices) associated with MRSA colonization. Swabs were collected from the nares, throat, axillae, groin area, and perirectal area for S. aureus colonization. Data on sociodemographic characteristics, medical conditions, and sexual history were collected. Multivariate logistic regression models evaluated factors associated with carriage. We studied 550 HIV-infected adults with a median age of 42 years; 93% were male; and race/ethnicity was white for 46%, African American for 35%, and other for 19%. Median CD4 count was 529 cells/mm, 11% had a history of a MRSA infection, and 21% had a sexually transmitted infection within the last year, including 8% with syphilis. One hundred eighty (33%) were colonized with S. aureus and 22 (4%) with MRSA. The most common location for carriage was the nares, followed by the perigenital area (groin or perirectal area). Factors associated with MRSA carriage in the multivariate analyses included a sexually transmitted infection in the last year (odds ratio [OR], 4.2; p < 0.01), history of MRSA infection (OR, 9.4; p < 0.01), and African American compared with white race/ethnicity (OR, 3.5; p = 0.01). In separate multivariate models, syphilis, nongonococcal urethritis, and public bath use were also associated with MRSA carriage (all p < 0.01). In conclusion, a history of recent sexually transmitted infections, including syphilis and urethritis, was associated with MRSA carriage. These data suggest that high-risk sexual activities may play a role in MRSA transmission.