Background: This study aims to find diets with low price and low climate impact, yet fulfilling all nutritional requirements. Methods: Optimization by linear programming. The program constrains 33 nutrients to fulfill Dutch dietary requirements. In a second cycle, the upper boundary for climate impact through greenhouse gas emissions (GHGE) is set to 1.6 kg carbon dioxide equivalents/day (CO2eq). In a third cycle, the costs are set on €2.50 as a constraint. The objective function of the optimization maximized the most consumed food products (n = 206) for male and female adults separately (age 31–50). Results: A diet of 63 popular and low priced basic products was found to deliver all required nutrients at an adequate level for both male and female adults. This plant-based, carbohydrate and fiber-rich diet consists mainly of wholegrain bread, potatoes, muesli, open-field vegetables and fruits. The climate impact of this diet is very low (1.59 kg CO2eq/day) compared to the average Dutch diet. By constraining costs, a low carbon diet of €2.59/day is possible. Conclusions: A two-person diet consisting of 63 products and costing €37 per week can simultaneously be healthy and yet have half the average climate impact. Linear programming is a promising tool to combine health and sustainability on both societal and individual levels.