Background Atrial fibrillation (AF) is a leading cause of preventable stroke in Australia. Given that anticoagulation therapy can significantly reduce this stroke risk, we sought to characterise anticoagulation use in Indigenous and non-Indigenous Australians with AF. Methods Administrative, clinical and prescription data from patients with AF were linked. Anticoagulation use was characterised according to guideline-recommended risk scores and Indigenous status. Results 19,613 individuals with AF were studied. Despite a greater prevalence of other risk factors, Indigenous Australians were significantly younger than their non-Indigenous counterparts (p < 0.001) and thus had lower CHADS2- (1.19 ± 0.32 vs 1.99 ± 0.47, p < 0.001) and CHA2DS2VASc-scores (1.47 ± 0.03 vs 2.82 ± 0.08, p < 0.001). Correspondingly, the percentage of Indigenous Australians with CHADS2 ≥ 2 (39.6% vs 44.1%, p < 0.001) and CHA2DS2VASc-scores ≥ 2 (62.9% vs 78.8%, p < 0.001) was also lower. Indigenous Australians, however, had greater rates of under- and over-anticoagulation. Overall, 72.1% and 68.9% of Indigenous and non-Indigenous Australians with CHADS2 scores ≥ 2, and 76.3% and 71.3% with CHA2DS2VASc scores ≥ 2, were under-anticoagulated. Similarly, 27.4% and 24.1% of Indigenous and non-Indigenous Australians with CHADS2 scores = 0, and 24.0% and 16.7% with CHA2DS2VASc-scores = 0, were over-anticoagulated. In multivariate analyses, Indigenous Australians were more likely to receive under- or over-anticoagulation according to CHADS2- or CHA2DS2VASc-score (p = 0.045 and p < 0.001 respectively). Conclusion Anticoagulation for AF is frequently not prescribed in accordance with guideline recommendations. Under-anticoagulation in those at high stroke risk, and over-anticoagulation in those at low risk, is common and more likely in Indigenous patients with AF. Improving adherence to guideline recommendations for anticoagulation in AF may reduce both ischaemic and haemorrhagic strokes in Indigenous and non-Indigenous Australians.