The objective of this study was to estimate the caries impact of providing training in infant feeding guidelines to workers at Brazilian public primary care clinics. In a cluster-randomized controlled trial (n = 20 clinics), health care workers either were trained in guidelines for infant nutrition, stressing healthful complementary feeding, or were assigned to a ‘usual practices’ control, which allowed for maternal counseling at practitioner discretion. Training occurred once; the amount of counseling provided to mothers was not assessed. Eligible pregnant women were enrolled to follow health outcomes in their children. Early childhood caries (ECC) was measured at age three years (n = 458 children). The overall reductions in ECC (relative risk, 0.92; 95%CI, 0.75, 1.12) and severe ECC (RR, 0.87; 95%CI, 0.64, 1.19) were not statistically significant. There was a protective effect among mothers who remained exclusively at the same health center (S-ECC RR, 0.68; 95%CI, 0.47, 0.99) and among those naming the health center as their principal source of feeding advice (S-ECC RR, 0.53; 95%CI, 0.29, 0.97). Health care worker training did not yield a statistically significant reduction in caries overall, although caries was reduced among children of mothers more connected to their health centers.