Sustainable diets are nutritious, culturally acceptable and have low environmental impact. The aim of this study was to identify sustainable diets among actual self-selected diets based on five national dietary surveys (Finland, France, Italy, Sweden, the United Kingdom), without ex ante assumptions concerning the food content of diets. Using nutrient intakes and dietary greenhouse gas emissions as active variables, energy-adjusted multiple factor analysis and agglomerative hierarchical clustering were applied to identify clusters of diets. The cluster with the lowest dietary GHGE had the lowest nutritional quality. Another cluster displayed a good compromise between nutritional quality and dietary GHGE (21% lower than the average of observed diets) and was therefore considered as more sustainable than the other clusters. Compared to the rest of the sample, diets in the more sustainable cluster were characterized by a larger quantity of plant-based products and lower quantities of meats, soft drinks and alcoholic beverages. The average diet in this cluster contained approximately 1000 g per day (g/d) of plant-based products (including 400 g/d of fruit and vegetables, 100 g/d of juices and 500 g/d of other plants) and 400 g/d of animal-based products (including 100 g/d of meat/fish/eggs of which livestock meat represented 20 g/d, 50 g/d of animal-based composite dishes, 30 g/d of cheese and 220 g/d of other dairy products). We concluded that exclusion of entire food categories (e.g., meat) is not necessary to improve the sustainability of European diets.