Background We sought to determine whether gay men would be willing to increase syphilis testing and partner notification, and assessed the possible epidemiological impact these changes might have in the Australian population. Methods: We conducted an online survey (n = 2306) and focus groups to determine whether interventions to increase testing for syphilis and enhanced partner notification are likely to be acceptable to gay men in Australia. An individual-based mathematical model was developed to estimate the potential population-level impact of changes in these factors. Results: Of all men surveyed, 37.3% felt they should test more frequently for sexually transmissible infections. Men who recent unprotected anal intercourse with casual partners and men who reported a higher number of partners were more likely to indicate a greater willingness to increase testing frequency. HIV-positive men were more likely to indicate that their frequency of syphilis testing was adequate, incorporated as part of their regular HIV monitoring. Lack of convenience was the main barrier reported. Partner notification was broadly acceptable, although perceived stigma presented a potential barrier. The mathematical model indicated that increasing testing rates would have a substantial impact on reducing rates of syphilis infection among gay men and partner notification would further reduce infections. Conclusions: Interventions promoting testing for syphilis among gay men and increases in partner notification may be acceptable to gay men and are likely to result in decreased infection rates. Rapid testing and modern communication technologies could strengthen these interventions, and have an impact on the syphilis epidemic.