The enteric protozoa, Cryptosporidium, Giardia and Entamoeba histolytica, cause diarrhea in children. We investigated the association of enteric protozoan-associated diarrheal illness with the nutritional status and growth of preschool children in Dhaka, Bangladesh. The subjects were 221 children aged 2–5 years who were followed prospectively for diarrheal illness for 3 years. The weight and height of the children were measured at entry and at 4-month intervals. Cryptosporidium and E. histolytica were diagnosed with commercially available stool antigen detection kits. Giardia was diagnosed by conventional microscopy. Cryptosporidium- and Giardia-associated diarrheal illness was not associated with the growth of the children. Children with E. histolytica-associated diarrheal illness had lower weight for age Z-score changes (−0.103 ± 0.120 vs. 0.176 ± 0.052, P = 0.038). Similarly, the change in height for age Z-score was lower in children with E. histolytica-associated diarrheal illness (−0.348 ± 0.186 vs. 0.142 ± 0.08, P = 0.018). Children with E. histolytica-associated diarrheal illness were 2.93 times (95% CI 1.01–8.52, P = 0.047) more likely to be malnourished and 4.69 times (95% CI 1.55–14.18, P = 0.006) more prone to be stunted. Entamoeba histolytica-associated diarrheal illness was negatively associated with the growth of preschool children.