Background: Sexually-transmitted infection (STI) acquisition continues among HIV-infected individuals. HIV-syphilis co-infection has been shown to increase HIV transmissibility to sexual partners. The requirement of military members to move between duty stations may create instability and put them at risk for acquiring STIs. We evaluated the association between moves and incident syphilis in the DoD HIV Natural History Study (NHS). Methods: The NHS is a cohort of HIV+ DoD beneficiaries seen bi-annually since 1986. Analyses were limited to those enrolled until 2011, with at least one syphilis screening and confirmatory test. Incident syphilis was defined as a negative non-treponemal test and a subsequent positive non-treponemal test. A move was defined as a change in the first 3 zipcode digits at their visit. Weibull analyses were used for association. Results: Among 4471 (30,378 years of follow-up; mean 6.8 yrs/per person), 407 (9.1%) acquired syphilis. At baseline, our sample was primarily male (92%), Caucasian (44%) or African American (43%) and single (60%). In an adjusted model, compared to those that never moved, hazard ratios (HR) for syphilis incidence among those that moved 1-2 times per 10 years of follow-up was 0.57 (CI: 0.4-0.8), 1.71 for those that moved 2-4 times (CI: 1.2-2.4) and 3.83for those with >4 moves (CI: 3.0-4.9), adjusting for race, military rank, and marital status at enrollment. Being African American (HR 2.9; 2.3-3.7), Hispanic/Other (HR 2.0; 1.4-2.8) or single (HR1.4; 1.1-1.7) was also associated with syphilis incidence. Conclusions: Low rates of geographic location changes may be protective for acquiring syphilis due to the military expectation of moving but higher rates of movement do increase syphilis incidence. Racial and marital status associations with higher risk of syphilis incidence may guide education and prevention efforts. Additional research is warranted to identify behavioral aspects related to STI acquisition amongst military HIV-infected members.