The high prevalence of undernutrition, especially stunting, in Ethiopia hampers the country’s economic productivity and national development. One of the obstacles to overcome undernutrition is the relatively high cost of food for low economic groups. In this study, linear programming was used to (i) identify urban and rural nutritionally adequate food baskets (FBs) with the highest affordability for an Ethiopian family of five and (ii) create urban and rural FBs, optimized for cultural acceptability, which are affordable for a family with the lowest income. Nutritionally adequate rural and urban FBs with highest affordability cost as little as Ethiopian Birr (ETB) 31 and 38 (~USD 1.07 and 1.31), respectively, but have poor dietary diversity (16 and 19 foods). FBs that cost ETB 71.2 (~USD 2.45) contained 64 and 48 foods, respectively, and were much more similar to the food supply pattern reported by FAO (15% and 19% average relative deviation per food category). The composed FBs, which are affordable for the greater part of the Ethiopian population, may serve as a basis for the development of culturally acceptable food-based dietary guidelines. These guidelines would recommend a diet composed of approximately up to 60% cereals, up to 20% roots and tubers, 10% legumes, and 10% fruits and vegetables by weight, plus only a small share from animal foods.