There is great potential for reducing greenhouse gas emissions (GHGE) from public-sector meals. This paper aimed to develop a strategy for reducing GHGE in the Swedish school food supply while ensuring nutritional adequacy, affordability, and cultural acceptability. Amounts, prices and GHGE-values for all foods and drinks supplied to three schools over one year were gathered. The amounts were optimized by linear programming. Four nutritionally adequate models were developed: Model 1 minimized GHGE while constraining the relative deviation (RD) from the observed food supply, Model 2 minimized total RD while imposing stepwise GHGE reductions, Model 3 additionally constrained RD for individual foods to an upper and lower limit, and Model 4 further controlled how pair-wise ratios of 15 food groups could deviate. Models 1 and 2 reduced GHGE by up to 95% but omitted entire food categories or increased the supply of some individual foods by more than 800% and were deemed unfeasible. Model 3 reduced GHGE by up to 60%, excluded no foods, avoided high RDs of individual foods, but resulted in large changes in food-group ratios. Model 4 limited the changes in food-group ratios but resulted in a higher number of foods deviating from the observed supply and limited the potential of reducing GHGE in one school to 20%. Cost was reduced in almost all solutions. An omnivorous, nutritionally adequate, and affordable school food supply with considerably lower GHGE is achievable with moderate changes to the observed food supply; i.e., with Models 3 and 4. Trade-offs will always have to be made between achieving GHGE reductions and preserving similarity to the current supply.