Child nutrition is one key factor that determines the outcome of human development and even influences the later quality of one’s life. Knowledge about nutrition and health is gained throughout childhood, yet there is limited research on the nutrition knowledge of nursery school children in Kenya. Much of the research assessing nutrition practices in early childhood programs has focused on the adequacy of foods that are served to children. The objectives of this study were to assess nutrition knowledge of preschoolers and assess their perception of what they would consider good food; and to evaluate their teacher knowledge and how this is influencing teaching of nutrition education. The study adopted a cross sectional study design consisting of 365 preschoolers from 36 nursery schools in Kisumu Municipality-Kenya and 146 ECD teachers. Stratified Cluster sampling was used in selecting all the participants. Study results showed that the overall mean nutrition knowledge score of the children was 51.7%. Few children (39.2%) were aware of the foods that should be eaten more frequently by them. There were significant differences between the children’s mean scores by their age (F = 96.46, p = 0.000). Children who were taught by teachers with previous training in Early Childhood Development scored higher that those children who were taught by teachers without the training. Mean nutrition knowledge score of the teachers was 53.3%. Only 22.6% of teachers were aware that goiter is caused by iodine deficiency while 46.6% were aware of foods rich in vitamin C and A. The study recommends training of nutrition education and closer collaboration between teachers and parents in teaching young children good nutrition. The government and relevant education institutions should also reinforce nutrition education in nursery school according to the education policy and to facilitate teaching materials for the same.