Current food consumption patterns must be revised in order to improve their sustainability. The nutritional, environmental, and economic consequences of these dietary patterns must be taken into consideration when diet guidelines are proposed. This study applied a systematic optimization methodology to define sustainable dietary patterns complying with nutritional, environmental, and economic issues. The methodology was based on a multi-objective optimization model that considered a distance-to-target approach. Although the three simultaneous objectives (maximal nutritional contribution, minimal greenhouse gas emissions, and minimal costs) could be divergent, the proposed model identified the optimal intake of each food product to achieve the maximal level of nutritional, environmental, and economic diets. This model was applied to six different eating patterns within the Spanish context: one based on current food consumption and five alternative diets. The results revealed that dietary patterns with improved nutritional profiles and reduced environmental impacts could be defined without additional costs just by increasing the consumption of vegetables, fruits, and legumes, while reducing the intake of meat and fish.