Background Simplified periodontal therapy might be a pragmatic strategy for public health programmes targeting Indigenous Australian adults. The objective of this randomized controlled trial was to evaluate oral health effects of single-visit, non-surgical periodontal therapy compared to no treatment. Methods This parallel-group, randomized, open label clinical trial enrolled 273 Indigenous Australians aged ≥18 years with periodontitis. Intervention participants received full-mouth periodontal scaling and root planing during a single visit while the control group received no treatment. Endpoints were summary variables derived from clinical assessments of probing depth, clinical attachment loss, plaque, calculus and gingival bleeding before treatment and 3 months later. Results Endpoints could be calculated for 169 participants with follow-up data. Compared to the control group, there were statistically significant reductions in extent of shallow pockets: PD ≥4 mm (mean difference -2.86, [95% CI -5.01 to -0.71], p = 0.009) and gingival bleeding (mean difference -0.25, [95% CI -0.43 to -0.08], p = 0.005) but not deeper pockets PD ≥5 mm (mean difference -0.48, [95% CI -1.78 to 0.82], p = 0.468) or plaque scores. Conclusions Periodontal therapy produced improvements in shallow periodontal pockets and measures of gingival bleeding in these Indigenous Australians.