Background: Remote Aboriginal communities in Australia have substantially higher rates of chlamydia (CT), gonorrhoea (NG) and trichomoniasis (TV) diagnosis compared with non-Indigenous people, despite many years of programme and policy aimed at reducing disparity. Methods: 'STRIVE' is a stepped wedge cluster randomised controlled trial, underway in 68 remote Aboriginal communities. The primary objective is to assess if a sexual health quality improvement programme within primary care clinics improves STI management and in turn reduces STI prevalence. Data is extracted from both patient management systems and from laboratories. To evaluate the impact of the trial, the largest STI prevalence study in Aboriginal people has been undertaken twice. Results: In the first year of the trial, testing rates have improved overall by 27% at 21 sites and by 50% or more at 11 sites. In 2011, baseline prevalences for CT and NG (n = 2483) and TV (n = 1848) among 16-34 year olds were 9%, 7% and 13% respectively. Highest prevalences were reported among 16-19 year olds for CT 13% (95% CI; 10.8-16.4), NG, 12% (95% CI; 9.7-15.1) and TV, 17%(95% CI; 13.7-21.1). There were 17,848 STI tests conducted in 2010 and among females aged 16-34; 33.3% had > 1 STI (highest in 16-19 year olds: 48.9%) and 21.3% of males had > 1 STI (highest in 16-19 year olds:33.4%). The most frequent co-infection was CT and NG which was found in 3.4% of females (highest in 16-19 year olds: 8.6%) and 3.9% of males (highest in 16-19 year olds:10.1%). Discussion: STRIVE has provided information not previously available in regard to a comprehensive epidemiological picture of STI morbidity and health service responses in remote Aboriginal communities and highlights work required especially among young people. The results of STRIVE may be of relevance to other areas globally with STI endemic rates.