Observational studies and nonrandomized trials support an association between periodontal disease and atherosclerotic vascular disease. Both diseases occur frequently in Aboriginal Australians. We hypothesized that nonsurgical periodontal therapy would improve measures of arterial function and structure that are subclinical indicators of atherosclerotic vascular disease. This parallel-group, randomized, open label clinical trial enrolled 273 Aboriginal Australians aged ≥18 years with periodontitis. Intervention participants received full-mouth periodontal scaling during a single visit, whereas controls received no treatment. Prespecified primary end points measured 12-month change in carotid intima-media thickness, an indicator of arterial structure, and 3- and 12-month change in pulse wave velocity, an indicator of arterial function. ANCOVA used complete case data to evaluate treatment group differences. End points could be calculated for 169 participants with follow-up data at 3 months and 168 participants at 12 months. Intima-media thickness decreased significantly after 12 months in the intervention group (mean reduction=-0.023 [95% confidence interval {CI}, -0.038 to -0.008] mm) but not in the control group (mean increase=0.002 [95% CI, -0.017 to 0.022] mm). The difference in intima-media thickness change between treatment groups was statistically significant (-0.026 [95% CI, -0.048 to -0.003] mm; P=0.03). In contrast, there were no significant differences between treatment groups in pulse wave velocity at 3 months (mean difference, 0.06 [95% CI, -0.17 to 0.29] m/s; P=0.594) or 12 months (mean difference, 0.21 [95% CI, -0.01 to 0.43] m/s; P=0.062). Periodontal therapy reduced subclinical arterial thickness but not function in Aboriginal Australians with periodontal disease, suggesting periodontal disease and atherosclerosis are significantly associated.