Background: Indigenous Australians experience an overwhelming burden of chronic disease, including cardiovascular diseases. Periodontal disease (inflammation of the tissues surrounding teeth) is also widespread, and may contribute to the risk of cardiovascular diseases via pathogenic inflammatory pathways. This study will assess measures of vascular health and inflammation in Indigenous Australian adults with periodontal disease, and determine if intensive periodontal therapy improves these measures over a 12 month follow-up. The aims of the study are: (i) to determine whether there is a dose response relationship between extent and severity of periodontal disease and measures of vascular health and inflammation among Indigenous Australian adults with moderate to severe periodontal disease; and (ii) to determine the effects of periodontal treatment on changes in measures of vascular health and inflammation in a cohort of Indigenous Australians. Methods/Design. This study will be a randomised, controlled trial, with predominantly blinded assessment of outcome measures and blinded statistical analysis. All participants will receive the periodontal intervention benefits (with the intervention delayed 12 months in participants who are randomised to the control arm). Participants will be Indigenous adults aged 25 years from urban centres within the Top End of the Northern Territory, Australia. Participants assessed to have moderate or severe periodontal disease will be randomised to the study's intervention or control arm. The intervention involves intensive removal of subgingival and supragingival calculus and plaque biofilm by scaling and root-planing. Study visits at baseline, 3 and 12 months, will incorporate questionnaires, non-fasting blood and urine samples, body measurements, blood pressure, periodontal assessment and non-invasive measures of vascular health (pulse wave velocity and carotid intima-media thickness). Primary outcome measures are pulse wave velocity and carotid intima-media thickness. Discussion. The study will assess the periodontal-cardiovascular disease relationship among Indigenous Australian adults with periodontal disease, and the effectiveness of an intervention aimed at improving periodontal and cardiovascular health. Efforts to understand and improve Indigenous oral health and cardiovascular risk may serve as an important means of reducing the gap between Indigenous and non-Indigenous health in Australia. Trial Registration. Australia and New Zealand Clinical Trials Register (ANZCTR): ACTRN12610000817044.