Recent studies have reported overall increasing rates of syphilis with a high rate of human immunodeficiency virus (HIV) co-infection. However, there is little information about factors influencing syphilis treatment failure and/or re-infection in HIV co-infected patients. We conducted a study to evaluate factors associated with syphilis treatment failure/re-infection in HIV co-infected patients. We reviewed 3542 medical records of HIV-infected patients from January 2005 to December 2007 followed up at HIV Clinic in New York City. Patients were categorized by rapid plasma regain titer (RPR) into success/serofast (4-fold decrease in RPR by 12 months after treatment, RPR conversion to nonreactive, persistently stable reactive RPR with no 4-fold increase), and failure/re-infection (failure to decrease 4 folds in RPR by 12 months after treatment, 4-fold increase in RPR from baseline). Among a total of 156 patients who met the eligibility criteria, 122 (78.2%) were under success/serofast category, and 34 (21.8%) were under failure/re-infection category. HIV viral load, CD4 cell count, and use of highly active antiretroviral therapy (HAART) were not associated with syphilis treatment failure/re-infection. However, early syphilis stage (OR: 11.036, 95%CI: 2.499 - 48.740, P = 0.002) and high (> 1:64) RPR titers (OR: 715.921, 95%CI: 422.175 - 23 113.396, P < 0.001) were significantly associated. No correlations were seen with depressed immune states with syphilis treatment failure and/or re-infection. However, association with early stage syphilis suggests that risky psychological sexual behaviors may be the most important leading factor, emphasizing needs for safe sex education.