Children in developing countries often face multiple micronutrient deficiencies. Introduction of zinc-fortified water can increase zinc intake, but additional recommendations are required to address overall diet nutrient adequacy. We developed and tested food-based recommendations (FBRs) that included zinc-fortified water for children aged between 4 and 6 years from rural Kenya to achieve the best possible nutrient adequacy. Dietary intakes of 60 children aged 4–6 years, from Kisumu West district, Kenya, were assessed using a quantitative multipass 24-hr recall. Linear programming model parameters were derived, including a list of foods consumed, median serving sizes, and distribution of frequency of consumption. By using the Optifood linear programming tool, we developed FBRs for diets including zinc-fortified water. FBRs with nutrient levels achieving ≥70% recommended nutrient intake (RNI) of the World Health Organization/Food and Agriculture Organization of the United Nations RNI for most of the 12 considered nutrients were selected as the final recommendations for the children. With no FBRs and no zinc-fortified water, percent RNI coverage range was between 40% and 76% for zinc, improving to 66–101% after introduction of zinc-fortified water. The final set of FBRs achieved nutrient adequacy for all nutrients except for vitamin A (25% RNI) and folate (68% RNI). Introduction of zinc-fortified water combined with FBRs will likely improve the nutrient adequacy of diets consumed by children in Kenya but needs to be complemented with alternative interventions to ensure dietary adequacy.