Nearly half of women of reproductive age (WRA) in Cambodia are anemic. To guide interventions, national data on nutritional causes of anemia, including iron deficiency and vitamin A deficiency, are needed. In 2012, a national household survey in WRA on antibodies to routine vaccine-preventable disease immunity was performed. We used serum samples from this survey to estimate the prevalence of iron and vitamin A deficiency in 2112 Cambodian WRA, aged 15 to 39 years. Iron deficiency was classified as low or marginal iron stores (ferritin concentrations corrected for inflammation <15 μg/L and <50 μg/L respectively; Fer), iron deficient erythropoiesis (soluble transferrin receptor concentrations >8.3 mg/L; sTfR), or low total body iron (TBI) derived from Fer and sTfR concentrations (<0 mg/kg). Vitamin A status was classified using retinol binding protein (RBP) concentrations corrected for inflammation as deficient (<0.70 μmol/L) or marginal (<1.05 μmol/L. Overall, the prevalence of low iron stores, low TBI and iron deficient erythropoiesis was 8.1%, 5.0% and 9.3% respectively. Almost 40% of the women had marginal iron stores. Iron status was better in women living in urban areas compared to rural areas (p < 0.05 for TBI and sTfR). The prevalence of vitamin A deficiency was <1%. These findings suggest that the contribution of iron and vitamin A deficiency to the high prevalence of anemia in Cambodian WRA may be limited. The etiology of anemia in Cambodia needs to be elucidated further to guide current policies on anemia.