This study documented existing knowledge on traditional fruits, vegetables and pulses in Kenya and Ethiopia. The aim was to identify neglected and underutilized species with high potential for food security, for their economic value and contribution to sustainable agriculture, based on a literature review and confirmation of existing data by local experts. In order of priority, the top 5 fruit species in Kenya are Tamarindus indica L., Adansonia digitata L., Sclerocarya birrea (A.Rich.) Hochst, Balanites aegyptiaca (L.) Delile, and Ziziphus mauritiana Lam., for vegetables are Amaranthus spp., Vigna unguiculata (L.) Walp., Solanum spp., and Cleome gynandra L. Top fruits in Ethiopia are Balanites aegyptiaca (L.) Delile, Ziziphus spina-christi (L.) Desf., Cordeauxia edulis Hemsl., Cordia africana Lam., and Mimusops kummel A. DC., for vegetables are Brassica carinata A. Braun, Cucurbita pepo L., and Amaranthus spp. In both countries, priority pulse species (no ranking) are Phaseolus lunatus L., Sphenostylis stenocarpa (A.Rich.) Harms, Mucuna pruriens (L.) DC., Lablab purpureus (L.) Sweet, and Cajanus cajan (L.) Millsp. Generally, these priority species are good sources of key nutrients known for their inadequate dietary intakes in sub-Saharan Africa, represent a safety net for household income, and contribute positively to ecosystem resilience in existing agricultural systems. Complete, accurate and reliable nutrient composition data are needed to raise consumer awareness about their nutritional and health benefits. Since women play a central role in traditional food systems, their empowerment, and hence resilience, increase the positive impact they can have on the households’ dietary diversity. In particular, introducing small-scale processing techniques and marketing strategies could enhance their supply and consumption.