Food and nutrition insecurity are pressing global issues, pertinent to the United Nations’ Sustainable Development Goal 2 (zero hunger). About 1 in 10 people globally are food insecure, with both the COVID-19 pandemic and the Ukraine-Russia crisis exacerbating the problem, partly due to unprecedented shortages in major food commodities, such as wheat, rice, and sunflower oil. Food and nutrition security have been negatively impacted in sub-Saharan African countries like Nigeria and Uganda where, prior to both crises, 25% of the population were already food insecure and children under five and women of reproductive age faced severe undernutrition, micronutrient deficiencies, and their associated health challenges. The recent crises have highlighted the need for a paradigm shift from relying on a few crops to a diversified, sustainable food system that harnesses the potential of neglected and underutilized species (NUS) for food and nutrition insecurity solution, especially in low and middle-income countries. Despite their abundance (>100 edible species) and high nutritional value, various political, socio-cultural, and infrastructural factors have deterred commercialization and utilization of NUS in sub-Saharan Africa. Moreover, there are limited sophisticated studies on many of NUS local to the region. This review aimed to discuss selected NUS, peculiar to Nigeria, namely, African walnut (Tetracarpidium conophorium), African breadfruit (Treculia africana), and Uganda, namely, sesame (Sesamus indicum L.) and pigeon pea (Cajanus cajan L.), and their potential to sustainably contribute towards improved food and nutrition security. The crops are briefly described, and their indigenous uses, nutritional value and medicinal properties highlighted. Issues relating to their production, processing, consumption, and exportation are reviewed considering their contribution towards sustainable food systems.