To our knowledge, the relationships among soil zinc, serum zinc and children’s linear growth have not been studied geographically or at a national level in any country. We use data from the cross-sectional, nationally representative Ethiopian National Micronutrient Survey (ENMS) (n = 1776), which provided anthropometric and serum zinc (n = 1171) data on children aged 6–59 months. Soil zinc levels were extracted for each child from the digital soil map of Ethiopia, developed by the Africa Soil Information Service. Children’s linear growth was computed using length/height and age converted into Z-scores for height-for-age. Multi-level mixed linear regression models were used for the analysis. Nationally, 28% of children aged 6–59 months were zinc deficient (24% when adjusted for inflammation) and 38% were stunted. Twenty percent of households in the ENMS were located on zinc-deficient soils. Soil zinc (in mg/kg) was positively associated with serum zinc (in µg/dL) (b = 0.9, p = 0.020) and weight-for-height-Z-score (b = 0.05, p = 0.045) but linear growth was not associated with soil zinc (p = 0.604) or serum zinc (p = 0.506) among Ethiopian preschool children. Intervention studies are needed to determine whether there are causal links between soil and human zinc status.