Background: Effective strategies for improving eating habits and dietary intake in preschool-ers are essential for reducing the risk of chronic non-infectious diseases in later life. The aim of this study was to evaluate the effect of long-term nutrition education for 3- to 6-year-olds on parental nutrition knowledge. Methods: The study was conducted as part of the “Colorful Eating is Healthy Eating” nutrition education program that has been implemented in kindergartens in Lublin since 2016. A total of 11 kindergartens were involved in this stage of the program, and 733 parents consented to participate in the project. The study was divided into three stages. In the first stage all parents completed a questionnaire containing 54 items. In the next stage, 211 children from four randomly selected kindergartens participated in the “Colorful Eating Is Healthy Eating” educational program that lasted 7 months. In the third stage of the study, the parents of children who had completed the 7-month educational program and the parents of control group children once again completed the questionnaire. Results: A positive outcome of the educational program was that it contributed to a decrease in the consumption of sweetened hot beverages (p = 0.005) and an increase in water intake (p = 0.001). The nutrition education program was also successful in reducing the consumption of sweets. Children’s education improved the parents’ knowledge about dietary sources of fiber and the recommended fiber intake, and it contributed to the awareness that breakfast is the most important meal of the day. The program did not enhance the parents’ knowledge about snacking between meals or the role of sweetened beverages in dental caries, overweight and obesity. Conclusions: Long-term multi-stage nutrition education for children aged 3 to 6 years can be helpful in shaping families’ eating habits and improving parental nutrition knowledge. However, the program was less effective in eliminating the respondents’ preference for sweet-tasting foods.