Prevalence estimates of various bacterial sexually transmitted infections in South Africa have declined considerably since the mid-1990s. Syphilis among pregnant women, for example, declined from 10.8% in 1998 to 2.8% in 2001. We used Pearson's correlation coefficients to estimate the association between the prevalence of syphilis/male urethral discharge/male genital ulcers and the peak HIV prevalence at a district and provincial level in the early and late phases of the HIV epidemic in South Africa. Prevalence estimates of syphilis, male urethral discharge and male genital ulcers during the period preceding the peak HIV prevalence were all positively correlated with the peak HIV prevalence at a provincial level (Pearson's correlation coefficient [r] = 0.83, p = 0.006; r = 0.66, p = 0.052; r = 0.79, 0.011, respectively). These relationships all switched to a negative association later in the HIV epidemic at a provincial level (r = -0.53, p = 0.14; r = -0.73, p = 0.130; r = -0.54, p = 0.027, respectively). AIDS mortality may have played an important role in the decline of bacterial sexually transmitted infections such as syphilis in this region. Consequently, the relatively recent scale-up of antiretroviral therapy may result in a resurgence of syphilis and other sexually transmitted infections as observed in high-income countries.