We aim to identify the dietary changes to improve nutrition and reduce diet-related greenhouse gas emission (GHGE) simultaneously in Brazil, taking into account the heterogeneity in food habits and prices across the country. Food consumption and prices were obtained from two nationwide surveys (n = 55,970 households and 34,003 individuals). Linear programming models were performed to design optimised diets most resembling the observed diets, and meeting different sets of constraints: (i) nutritional, for preventing chronic diseases and meeting nutrient adequacy; (ii) socio-cultural: by respecting food preferences; and (iii) environmental: by reducing GHGE by steps of 10%. Moving toward a diet that meets nutritional recommendations led to a 14% to 24% cost increase and 10% to 27% GHGE reduction, depending on the stringency of the acceptability constraints. Stronger GHGE reductions were achievable (up to about 70%), with greater departure from the current diet, but not achieving calcium and potassium goals. Diet cost increment tended to be mitigated with GHGE reduction in most models, along with reductions in red meat, chicken, eggs, rice, and high-fat sugar sodium foods.