Poor quality infant and young child (IYC) diets contribute to chronic under-nutrition. To design effective IYC nutrition interventions, an understanding of the extent to which realistic food-based strategies can improve dietary adequacy is required. We collected 24-h dietary recalls from children 6-23 months of age (n = 401) in two rural agro-ecological zones of Kenya to assess the nutrient adequacy of their diets. Linear programming analysis (LPA) was used to identify realistic food-based recommendations (FBRs) and to determine the extent to which they could ensure intake adequacy for 12 nutrients. Mean nutrient densities of the IYC diets were below the desired level for four to nine of the 10 nutrients analysed, depending on the age group. Mean dietary diversity scores ranged from 2.1 ± 1.0 among children 6-8 months old in Kitui County to 3.7 ± 1.1 food groups among children 12-23 months old in Vihiga County. LPA confirmed that dietary adequacy for iron, zinc and calcium will be difficult to ensure using only local foods as consumed. FBRs for breastfed children that promote the daily consumption of cows'/goats' milk (added to porridges), fortified cereals, green leafy vegetables, legumes, and meat, fish or eggs, 3-5 times per week can ensure dietary adequacy for nine and seven of 12 nutrients for children 6-11 and 12-23 months old, respectively. For these rural Kenyan children, even though dietary adequacy could be improved via realistic changes in habitual food consumption practices, alternative interventions are needed to ensure dietary adequacy at the population level.