This is the first study to investigate the efficacy of intravenous iron in treating fatigue in nonanemic patients with low serum ferritin concentration. In a randomized, double-blinded, placebo-controlled study, 90 premenopausal women presenting with fatigue, serum ferritin ≤ 50 ng/mL, and hemoglobin ≥ 120 g/L were randomized to receive either 800 mg of intravenous iron (III)-hydroxide sucrose or intravenous placebo. Fatigue and serum iron status were assessed at baseline and after 6 and 12 weeks. Median fatigue at baseline was 4.5 (on a 0-10 scale). Fatigue decreased during the initial 6 weeks by 1.1 in the iron group compared with 0.7 in the placebo group (P = .07). Efficacy of iron was bound to depleted iron stores: In patients with baseline serum ferritin ≤ 15 ng/mL, fatigue decreased by 1.8 in the iron group compared with 0.4 in the placebo group (P = .005), and 82% of iron-treated compared with 47% of placebo-treated patients reported improved fatigue (P = .03). Drug-associated adverse events were observed in 21% of iron-treated patients and in 7% of placebo-treated patients (P = .05); none of these events was serious. Intravenous administration of iron improved fatigue in iron-deficient, nonanemic women with a good safety and tolerability profile. The efficacy of intravenous iron was bound to a serum ferritin concentration ≤ 15 ng/mL. This study was registered at the International Standard Randomized Controlled Trial Number Register (www.isrctn.org) as ISRCTN78430425.