Anemia and low hemoglobin have been identified to increase Parkinson’s disease (PD) risk. This population-based cohort study investigated PD risk in newly diagnosed anemic patients by using data from the Taiwan National Health Insurance Research Database. All newly diagnosed anemic patients (n = 86,334) without a history of stroke, neurodegenerative diseases, traumatic brain injury, major operations, or blood loss diseases were enrolled. A cohort of nonanemic controls, 1:1 matched with anemic patients on the basis of the demographics and pre-existing medical conditions, was also included. Competing risk analysis was used to evaluate PD risk in anemic patients compared with that in their matched controls. The adjusted hazard ratio (aHR) of PD risk in the anemic patients was 1.36 (95% confidence interval [CI]: 1.22–1.52, p < 0.001). Iron deficiency anemia (IDA) patients tended to exhibit a higher PD risk (aHR: 1.49; 95% CI: 1.24–1.79, p < 0.001). Furthermore, Iron supplement did not significantly affect the PD risk: the aHRs for PD risk were 1.32 (95% CI: 1.07–1.63, p < 0.01) and 1.86 (95% CI: 1.46–2.35, p < 0.001) in IDA patients with and without iron supplementation, respectively. The population-based cohort study indicated newly diagnosed anemia increases PD risk.