Background: The Uzbekistan 1996 Demographic Health Survey reported 60.4% of women of reproductive age (WRA) had low hemoglobin concentrations (<120 g/L), and anemia was an important public health problem. Fortification of wheat flour was identified as an appropriate intervention to address anemia due to the ubiquitous consumption of wheat flour. A National Flour Fortification Program (NFFP) was implemented in 2005. Methodology/Principal Findings: After 3-years of the NFFP, a national survey using large country-lot quality assurance sampling was carried out to assess iron, folate, hemoglobin and inflammation status of WRA; the coverage and knowledge of the fortified first grade UzDonMakhsulot (UDM) flour/grey loaf program; and consumption habits of women to investigate the dietary factors associated with anemia. Estimated anemia prevalence was 34.4% (95% CI: 32.0, 36.7), iron depletion 47.5% (95% CI: 45.1, 49.9) and folate deficiency 28.8% (95% CI: 26.8, 30.8); the effect of inflammation was minimal (4% with CRP >5 mg/L). Severe anemia was more prevalent among folate deficient than iron depleted WRA. Presence of UDM first grade flour or the grey loaf was reported in 71.3% of households. Among WRA, 32.1% were aware of UDM fortification; only 3.7% mentioned the benefits of fortification and 12.5% understood causes of anemia. Consumption of heme iron-containing food (91%) and iron absorption enhancers (97%) was high, as was the consumption of iron absorption inhibitors (95%). Conclusions/Significance: The NFFP coincided with a substantial decline in the prevalence of anemia. Folate deficiency was a stronger predictor of severe anemia than iron depletion. However, the prevalence of iron depletion was high, suggesting that women are not eating enough iron or iron absorption is inhibited. Fortified products were prevalent throughout Uzbekistan, though UDM flour must be adequately fortified and monitored in the future. Knowledge of fortification and anemia was low, suggesting consumer education should be prioritized.