Achieving sustainable dietary change is essential for safeguarding human and environmental health. However, dietary recommendations based on broad food groups may not accurately reflect real-world realities because individuals select and consume dishes with multiple food items influenced by diverse context-specific factors. Therefore, here we explored the sustainability trade-offs of dietary choices at the dish level through an optimization modeling approach tested in Japan. We estimated the nutritional quality, price, and carbon footprint of major Japanese dishes and examined 16 dietary scenarios to identify options that meet the nutritional requirements and minimize carbon footprint. Overall, mixed diets contain more combinations of dishes that meet nutritional requirements with lower carbon footprints compared to more restrictive dietary scenarios. We argue that the approach developed here enables a better understanding of dietary trade-offs, complements existing methods, and helps identify sustainable diets by offering nuanced information at the national and sub-national levels.