The prevalence of trace elements deficiencies, vitamin A deficiency, anemia, and their relationships were investigated in a cross sectional study involving 243 children aged from 12 to 72 months in rural Vietnam. Serum levels of copper, zinc, selenium and magnesium were determined by inductively coupled plasma mass spectrometer and that of retinol by high performance liquid chromatography. Hemoglobin concentration in whole blood was measured by the cyanmethemoglobin method. The prevalence of deficiencies in zinc, selenium, magnesium, and copper was 86.9%, 62.3%, 51.9%, and 1.7%, respectively. On the other hand, 55.6% were anemic and 11.3% had vitamin A deficiency. Deficiency in two or more micronutrient was found in 79.4% of the children. Parameters associated significantly with anemia were selenium deficiency (OR 2.80 95% CI 1.63-4.80, p=0.0002) and serum retinol<1.05 micromol/L (OR 1.83, 95% CI 1.10-3.05, p=0.021). Magnesium deficiency (OR 3.09 95% CI 1.36-7.03) was found to be a risk factor for zinc deficiency and vice versa. The results indicate that micronutrient deficiencies are prevalent among preschool children in Vietnam. In addition, the results also demonstrate a strong relationship between selenium deficiency and anemia. Clearly, sustainable strategies are urgently required to overcome the problems in the country.