One cost-effective strategy for controlling iron deficiency is the fortification of staple foods or condiments with iron. We evaluated the effectiveness of fortifying fish sauce with NaFeEDTA for improving iron status in women of childbearing age in Vietnam in a double-blind intervention with randomization by village. All families in the selected villages were supplied with fish sauce that was either unfortified (Group C, 10 villages) or fortified with NaFeEDTA [9 mmol (500 mg) Fe/L, Group F, 11 villages] for 18 mo. The effect of fortification was assessed in the 576 women (n = 288/group) by measuring hemoglobin and serum ferritin (SF) at 6, 12, and 18 mo. Analysis of the group x time interaction using a repeated-measures test for each response demonstrated a significant effect of fortification on hemoglobin (P = 0.039) and log SF (P < 0.0001) in Group F with no significant changes in Group C. The prevalence of iron deficiency (SF < 12 microg/L) decreased from 22.3 to 4.0% and the prevalence of anemia (hemoglobin < 120 g/L) from 24.7 to 8.5% in Group F with no significant changes in Group C. NaFeEDTA fortification of fish sauce is an effective method for reducing the prevalence of iron deficiency in women in Vietnam.