There is a need for agriculture in sub-Saharan Africa to diversify into more nutrient-rich crops to meet the subcontinent’s nutritional needs in terms of micronutrients and reduce health risks related to high and rising rates of overweight/obesity. Many traditional African vegetables (TAVs) are nutrient-dense and have much potential to reduce malnutrition. These vegetables can also provide sustainable incomes to rural, urban and peri-urban farming communities. In addition to their high economic values and health benefits, most TAVs are amenable to be grown under low input conditions and even organically. However, TAVs are under-researched and underutilized across the vegetable value chain. This paper provides a detailed account of the value of TAVs, focusing on their importance, research and development progress, and future needs. To exploit the potential of TAVs, there is need for a more concerted research and development efforts including effective characterization of the nutrition and genetic profiles; enhancing adaptability and yield gains; and capacity development in value addition, postharvest handling, processing, marketing, and seed system development. Success in these areas depends on effective collaborations among national and international partners including the private seed sector, and government and non-governmental organizations working in the areas of agriculture, nutrition and health.