Background: The well-described biologic and epidemiologic associations of syphilis and HIV are particularly relevant to the military, as service members are young and at risk for sexually transmitted infections. We therefore used the results of serial serologic testing to determine the prevalence, incidence, and risk factors for incident syphilis in a cohort of HIV-infected Department of Defense beneficiaries. Methods: Participants with a positive nontreponemal test at HIV diagnosis that was confirmed on treponemal testing were categorized as prevalent cases, and participants with an initial negative nontreponemal test who subsequently developed a confirmed positive nontreponemal test were categorized as incident cases. Results: At HIV diagnosis, the prevalence of syphilis was 5.8% (n = 202). A total of 4239 participants contributed 27,192 person-years (PY) to the incidence analysis and 347 (8%) developed syphilis (rate, 1.3/100 PY; [1.1, 1.4]). Syphilis incidence was highest during the calendar years 2006 to 2009 (2.5/100 PY; [2.0, 2.9]). In multivariate analyses, younger age (per 10 year increase hazard ratio [HR], 0.8; [0.8-0.9]), male gender (HR, 5.6; [2.3-13.7]), non-European-American ethnicity (African-American HR, 3.2; [2.5-4.2]; Hispanic HR, 1.9; [1.2-3.0]), and history of hepatitis B (HR, 1.5; [1.2-1.9]) or gonorrhea (HR, 1.4; [1.1-1.8]) were associated with syphilis. Conclusions: The significant burden of disease both at and after HIV diagnosis, observed in this cohort, suggests that the cost-effectiveness of extending syphilis screening to at-risk military members should be assessed. In addition, HIV-infected persons continue to acquire syphilis, emphasizing the continued importance of prevention for positive programs.