BACKGROUND: Since 2005, Australian clinicians were advised to undertake quarterly syphilis testing for all sexually active HIV-positive men who have sex with men (MSM). We describe differences in syphilis testing frequency among HIV-positive MSM by clinic testing policies since this recommendation. METHODS: Three general practices, two sexual health clinics and two hospital HIV outpatient clinics provided data on HIV viral load and syphilis testing from 2006-2010. Men having >/=1 viral load test per year were included; >95% were MSM. We used Chi-2 tests to assess changes in syphilis testing frequency over time, and differences by clinic testing policy (opt-out, opt-in and risk-based). RESULTS: The proportion of men having HIV viral loads with same-day syphilis tests increased from 37% in 2006 to 63% in 2007 (p<0.01) and 68-69% thereafter. In 2010, same-day syphilis testing was highest in four clinics with opt-out strategies (87%, range:84-91%) compared with one clinic with opt-in (74%, p = 0.121) and two clinics with risk-based strategies (22%, range:20-24%, p<0.01). The proportion of men having >/=3 syphilis tests per year increased from 15% in 2006 to 36% in 2007 (p<0.01) and 36-38% thereafter. In 2010, the proportion of men having >/=3 syphilis tests in a year was highest in clinics with opt-out strategies (48%, range:35-59%), compared with opt-in (39%, p = 0.121) and risk-based strategies (8.4%, range:5.4-12%, p<0.01). CONCLUSION: Over five years the proportion of HIV-positive men undergoing syphilis testing at recommended frequencies more than doubled, and was 5-6 times higher in clinics with opt-out and opt-in strategies compared with risk-based policies.