Current diets of most nations either do not meet the nutrition recommendations or transgress environmental planetary boundaries or both. Transitioning toward sustainable diets that are nutritionally adequate and low in environmental impact is key in achieving the United Nations' Sustainable Development Goals. However, designing region-specific sustainable diets that are culturally acceptable is a formidable challenge. Recent studies have suggested that optimization algorithms offer a potential solution to the above challenge, but the evidence is mostly based on case studies from high-income nations using widely varying constraints and algorithms. Here, we employ nonlinear optimization modeling with a consistent study design to identify diets for 152 countries that meet four cultural acceptability constraints, five food-related per capita environmental planetary boundaries (carbon emissions, water, land, nitrogen, and phosphorus use), and the daily recommended levels for 29 nutrients. The results show that a considerable departure from current dietary behavior is required for all countries. The required changes in intake amounts of 221 food items are highly country-specific but in general point toward a need to reduce the intake of meat, dairy, rice, and sugar and an increase in fruits, vegetables, pulses, nuts, and other grains. The constraints for fiber, vitamin B12, vitamin E, and saturated fats and the planetary boundaries for carbon emissions and nitrogen application were the most difficult to meet, suggesting the need to pay special attention to them. The analysis demonstrates that nonlinear optimization is a powerful tool to design diets achieving multiple objectives.