Effective food-based dietary guidelines (FBDGs) are required to combat micronutrient deficiencies. This study aimed to develop a rigorous approach for designing population-specific FBDGs. A 4-phase approach based on linear programming analysis was used to design, test, and refine the FBDGs. This was illustrated for Malawian children. In phase I, the objective function minimized the difference in the energy contributed by different food groups between modeled and observed diets for 16 observed diet types, while preferentially selecting foods most often consumed. Constraints ensured nutrient adequacy and diet palatability. In phase II, the meal/snack patterns of the phase I modeled diets were examined to develop season-specific FBDGs. In phase III, the robustness of these FBDGs, for ensuring a nutritionally adequate diet, was tested. The objective function, in this analysis, minimized selected nutrient levels in the modeled diets (i.e., chose the “worst-case scenario”), while respecting the FBDGs, palatability, and energy constraints. The FBDGs were refined in phase IV. In the Malawian example used to illustrate our approach, the FBDGs promoted daily consumption of maize flour, small dry fish (≥20 g), leaf relish, and 2–3 snacks. The last mentioned included mangoes, in the food-shortage season, and pumpkin in the food-plenty season. In addition, legume relish was recommended in the food-shortage season. The approach presented here can be used to design and then test the robustness of FBDGs for meeting nutrient recommendations.