Background: Contact tracing is an important strategy in the control of sexually transmitted infections (STI) because it encourages individuals who may be unaware they have been exposed to an infection to be tested and treated. The aim of this study was to review STI contact tracing procedures in NSW by sexual health clinics (SHC), public health units (PHU) and general practitioners (GP). Methods: A questionnaire study carried out in 2004–2005 of SHC, PHU and a random sample of GP in NSW. SHC and PHU participated in structured interviews and GP completed questionnaires at educational workshops or through a mail-out. Interviews and questionnaires addressed current contact tracing practice and methods of improving the service. Results: All 35 SHC, 6/18 (33%) PHU and 172/212 (81%) of the GP who responded to the survey undertook contact tracing for STI. Chlamydia was the STI most commonly traced by SHC (34/35, 97%) and GP (165/172, 96%). HIV was the STI most commonly traced by PHU (5/6, 83%). Only 23/172 (13%) GP were familiar with the ‘Australasian contact tracing manual’. The commonest barriers to tracing for SHC and GP included patient reluctance (SHC 60%, GP 71%), and the lack of contact details for partners (SHC 46%, GP 60%). GP identified the availability of information for patients (82%) and more training (55%) as necessary resources for optimal contact tracing. Conclusions: SHC and GP frequently undertook contact tracing for some STI; PHU do so less frequently. Barriers to contact tracing are similar for all health-care providers. For GP, there is a need for increased training and the development of written policies and agreed pathways for referral.