This paper describes the epidemiology of a syphilis outbreak in remote Australia, and explores contributing factors and control strategies. Between 1 August 2000 and 31 January 2002, 74 cases of early syphilis (42 female, 32 male) were identified in 73 Kimberley residents. Syphilis rates in age groups 10–19 and 20–29 years were 583 and 439 per 100000 person years respectively. Factors contributing to the outbreak included incompleteness of sexually transmitted infection (STI) clinical management, untimely contact tracing, staffing and management issues, and poor community knowledge about STIs. Outbreak control strategies addressed factors that could be influenced by changes in health service delivery, and focused on providing education and support to health staff, and efforts to increase community knowledge about sexual health. Although some improvements have occurred, the outbreak is still continuing. Until open and honest discussion and a collaborative approach is taken toward STI problems affecting Indigenous Australians, outbreaks such as this will continue to occur.