Abstract Dietary modification has the potential to improve nutritional status and reduce environmental impacts of the food system. However, for many countries, the optimal composition of locally contextualized healthy and sustainable diets is unknown. The Gambia is vulnerable to climate-change-induced future water scarcity which may affect crop yields and the ability to supply healthy diets. This study identifies potential shifts in Gambian diets that could make diets healthier and reduce the associated agricultural water footprint (WF), and assesses the cost and affordability implications of such dietary changes. Gambian Integrated Household Survey (IHS) food consumption data was combined with market prices, food expenditure and agricultural WF data. Current dietary patterns were compared with World Health Organization (WHO) dietary guidelines and optimized using linear programming to identify least-cost diets that met nutrition recommendations and reduced agricultural water use. Optimization scenarios explored the maximum reduction in green water use that could be achieved with ‘culturally-acceptable’ dietary shifts, and the magnitude of shifts required to maintain green water use at current levels. On average, current diets provide adequate energy and have appropriate macronutrient composition. However, only 14% of households consume enough fruit and vegetables (F&Vs), and consumption of added sugars exceeds recommendations. With ‘culturally-acceptable’ changes in consumption, agricultural water use could decrease by 10%–13% or increase by 9%, depending on the baseline dietary pattern. Extreme dietary shifts will be required to maintain water use at 2015 levels with projected population growth. To meet WHO recommendations, dietary costs would increase by 43% compared to the current baseline. Healthy and green water-saving diets would require 48%–63% of average household expenditure to purchase, which is unaffordable for almost half of the population. F&Vs alone account for 31%–40% of the cost of optimized diets compared to 12% of current diets. Dietary modification has the potential to improve the nutritional quality of Gambian diets while reducing agricultural water use, but the required changes are likely to be unaffordable for a large proportion of the population. Improving availability and affordability of nutritious foods—particularly F&Vs—will be crucial for the accessibility of healthy and sustainable diets in the Gambian population.