Producing colored signals often requires consuming dietary carotenoid pigments. Evidence that food deprivation can reduce coloration, however, raises the question of whether other dietary nutrients contribute to signal coloration, and furthermore, whether individuals can voluntarily select food combinations to achieve optimal coloration. We created a two-way factorial design to manipulate macronutrient and carotenoid access in common mynas (Acridotheres tristis) and measured eye patch coloration as a function of the food combinations individuals selected. Mynas had access to either water or carotenoid-supplemented water and could either eat a standard captive diet or choose freely between three nutritionally defined pellets (protein, lipid or carbohydrate). Mynas supplemented with both carotenoids and macronutrient pellets had higher color scores than control birds. Male coloration tended to respond more to nutritional manipulation than females, with color scores improving in macronutrient- and carotenoid-supplemented individuals compared with controls. All mynas consuming carotenoids had higher levels of plasma carotenoids, but only males showed a significant increase by the end of the experiment. Dietary carotenoids and macronutrient intake consumed in combination tended to increase plasma carotenoid concentrations the most. These results demonstrate for the first time that consuming specific combinations of macronutrients along with carotenoids contributes to optimizing a colorful signal, and point to sex-specific nutritional strategies. Our findings improve our knowledge of how diet choices affect signal expression and, by extension, how nutritionally impoverished diets, such as those consumed by birds in cities, might affect sexual selection processes and, ultimately, population dynamics.