Community-associated methicillin-resistant Staphylococcus aureus (CA-MRSA) infections are well described among the general population, but little is known regarding the incidence of and predictors for recurrent CA-MRSA infections among HIV-infected persons. We retrospectively evaluated HIV-infected patients seen at the Naval Medical Center San Diego from January 1, 2000 to June 30, 2007 for wound culture-proven MRSA infections defined as community-associated based on Centers for Disease Control and Prevention (CDC) criteria. Data on skin/soft tissue infections (SSTIs) following an initial CA-MRSA infection were collected by review of medical records and culture results. Patients with or without recurrent infections were compared for predictors of recurrence using multivariate logistic regression models. Thirty-one (6.8%) of 458 patients with HIV had wound culture-proven CA-MRSA SSTIs for an incidence rate of 12.3 infections per 1000 person–years. Those who developed a MRSA infection had a mean age of 40 years, 97% were male, 58% were Caucasian, 23% were Hispanic, 16% were African American, and 3% were other; demographics were similar to the overall study population. Fourteen (41%) HIV patients with an initial MRSA infection had recurrent SSTIs; of these, seven (21%) had culture-confirmed recurrent CA-MRSA. The median time between infection recurrences was 4 months (range, 1–20 months). Suppressed HIV-1 RNA levels of less than 1000 copies per milliliter (odds ratio [OR] 0.14, p = 0.03) was associated with a lower rate of SSTI recurrence. In summary, HIV-infected persons have a high incidence of CA-MRSA skin/soft tissue infections and a high rate of recurrence. HIV control may be associated with a reduced risk of recurrent skin/soft tissue infections.