Objectives To determine the co-occurrence and epidemiological relationships of Chlamydia trachomatis (CT), Neisseria gonorrhoeae (NG) and Trichomonas vaginalis (TV) in a high-prevalence setting in Australia. Methods In the context of a cluster randomised trial in 68 remote Aboriginal communities, we obtained laboratory reports on simultaneous testing for CT, NG and TV by nucleic acid amplification tests in individuals aged ≤16 years and examined relationships between age and sex and the coinfection positivity. ORs were used to determine which infections were more likely to co-occur by demographic category. Results Of 13 480 patients (median age: 30 years; men: 37%) tested for all three infections during the study period, 33.3% of women and 21.3% of men had at least one of them, highest in patients aged 16-19 years (48.9% in women, 33.4% in men). The most frequent combination was CT/NG (2.0% of women, 4.1% of men), and 1.8% of women and 0.5% of men had all three. In all co-combinations, coinfection positivity was highest in patients aged 16-19 years. CT and NG were highly predictive of each other's presence, and TV was associated with each of the other two infections, but much more so with NG than CT, and its associations were much stronger in women than in men. Conclusions In this remote high-prevalence area, nearly half the patients aged 16-19 years had one or more sexually transmitted infections. CT and NG were more common dual infections. TV was more strongly associated with NG coinfections than with CT. These findings confirm the need for increased simultaneous screening for CT, NG and TV, and enhanced control strategies.