Background and objectives: Current dietary habits have substantial negative impacts on the health of people and the planet. This study aimed to develop a novel approach for achieving health-promoting and climate-friendly dietary recommendations for a broad range of consumers. Subjects and methods: Hierarchical clustering analysis was combined with linear programming to design nutritionally adequate, health-promoting, climate-friendly and culturally acceptable diets using Swedish national dietary data (n = 1797). Diets were optimised for the average consumption of the total population as well as for the dietary clusters. Results: Three dietary clusters were identified. All optimised diets had lower shares of animal-source foods and contained higher amounts of plant-based foods. These dietary shifts reduced climate impacts by up to 53% while leaving much of the diet unchanged. The optimised diets of the three clusters differed from the optimised diet of the total population. All optimised diets differed considerably from the food-group pattern of the EAT-Lancet diet. Conclusions: The novel cluster-based optimisation approach was able to generate alternatives that may be more acceptable and realistic for a sustainable diet across different groups in the population.