China's fast-paced socio-economic transformation has been accompanied by shifting diets towards higher shares of non starchy foods. Such trends change the dietary health risks but also potentially contribute to growing environmental problems, and thus necessitate an understanding of the links between nutritional quality and environmental impacts of Chinese diets. We assess the nutritional quality of over 21,500 individuals living in nine provinces during the 1997-2011 period and quantify their environmental footprints. Our study shows that the greenhouse gas emissions, water consumption and land appropriation of the average diet increased, driven by consumption of meat, cooking oil and other non-starchy foods. While increasing meat and oil consumption has lead to an increased burden on the environment and a reduction in the nutritional quality of Chinese diets, increases in other non-starchy foods has improved nutritional quality but with increased negative environmental consequences. Our findings identify trade-offs and synergies emerging from analysing the nutrition-environment nexus, and indicate challenges as well as opportunities in reducing environmental impacts while eliminating malnutrition.