Background: In addition to the traditional risk predictors, whether anemia is an early bio-marker of dementia, needs to be confirmed. Objective: This population-based cohort study aimed to investigate the dementia risk in patients with newly diagnosed anemia using data from the Taiwan National Health Insurance Research Database. Methods: All newly diagnosed anemia patients (n = 26,343) with no history of stroke hospitalization, central nervous disease other than dementia, psychiatric disorders, traumatic brain injury, major operations, or blood loss diseases, were enrolled. A group of non-anemic controls, 1:4 matched with anemic patients on the basis of demographics and comorbidities, was also included. A competing risk analysis was used to evaluate the dementia risk in anemic patients compared to that of their matched controls. Results: The adjusted subdistribution hazard ratio (SHR) of dementia risk in anemic patients was 1.14 (95% confidence interval [CI]: 1.08~1.21, p<0.001). Patients with iron supplements tended to exhibit a lower dementia risk (adjusted SHR: 0.84; 95% CI: 0.75~0.94, p=0.002) compared to patients without iron supplement. A subgroup analysis showed that a positive association between dementia and anemia existed in females, those aged 70 years and older, and patients without hypertension, diabetes, or hyperlipidemia. Conclusion: The present population-based cohort study identified that newly diagnosed anemia is a risk factor for dementia and also that iron supplementation was able to reduce the risk of dementia in people with iron deficiency anemia.