Background: Remote Australian Aboriginal communities have among the highest diagnosed rates of sexually transmissible infections (STIs) in the world. We did a trial to assess whether continuous improvement strategies related to sexual health could reduce infection rates. Methods: In this stepped-wedge, cluster-randomised trial (STIs in remote communities: improved and enhanced primary health care [STRIVE]), we recruited primary health-care centres serving Aboriginal communities in remote areas of Australia. Communities were eligible to participate if they were classified as very remote, had a population predominantly of Aboriginal people, and only had one primary health-care centre serving the population. The health-care centres were grouped into clusters on the basis of geographical proximity to each other, population size, and Aboriginal cultural ties including language connections. Clusters were randomly assigned into three blocks (year 1, year 2, and year 3 clusters) using a computer-generated randomisation algorithm, with minimisation to balance geographical region, population size, and baseline STI testing level. Each year for 3 years, one block of clusters was transitioned into the intervention phase, while those not transitioned continued usual care (control clusters). The intervention phase comprised cycles of reviewing clinical data and modifying systems to support improved STI clinical practice. All investigators and participants were unmasked to the intervention. Primary endpoints were community prevalence and testing coverage in residents aged 16–34 years for Chlamydia trachomatis, Neisseria gonorrhoeae, and Trichomonas vaginalis. We used Poisson regression analyses on the final dataset and compared STI prevalences and testing coverage between control and intervention clusters. All analyses were by intention to treat and models were adjusted for time as an independent covariate in overall analyses. This study was registered with the Australia and New Zealand Clinical Trials Registry, ACTRN12610000358044. Findings: Between April, 2010, and April, 2011, we recruited 68 primary care centres and grouped them into 24 clusters, which were randomly assigned into year 1 clusters (estimated population aged 16–34 years, n=11 286), year 2 clusters (n=10 288), or year 3 clusters (n=13 304). One primary health-care centre withdrew from the study due to restricted capacity to participate. We detected no difference in the relative prevalence of STIs between intervention and control clusters (adjusted relative risk [RR] 0·97, 95% CI 0·84–1·12; p=0·66). However, testing coverage was substantially higher in intervention clusters (22%) than in control clusters (16%; RR 1·38; 95% CI 1·15–1·65; p=0·0006). Interpretation: Our intervention increased STI testing coverage but did not have an effect on prevalence. Additional interventions that will provide increased access to both testing and treatment are required to reduce persistently high prevalences of STIs in remote communities. Funding: Australian National Health and Medical Research Council.