Honey bee colonies, foraging predominantly on a single pollen source, may encounter nutritional deficits. In the present study, we examined the nutritional resilience of honey bee colonies, testing whether foragers shift their foraging effort towards resources that complement a nutritional deficit. Eight honey bee colonies were kept in screened enclosures and fed for 1 week a pollen substitute diet deficient in a particular essential amino acid. Foragers were subsequently tested for a preference between the same diet previously fed, a different diet that was similarly deficient, or a diet that complemented the deficiency. Foragers preferred the complementary diet over the same or similar diets. Appetitive conditioning tests showed that bees were able to discriminate also between the same and similar diets. Overall, our results support the hypothesis that honey bees prefer dietary diversity, and that they do not just include novel sources but specifically target nutritionally complementary ones. Whereas we specifically focused on deficiencies in essential amino acids, we cannot rule out that bees were also complementing correlated imbalances in other nutrients, most notably essential fatty acids. The ability of honey bees to counter deficient nutrition contributes to the mechanisms which social insects use to sustain homeostasis at the colony level.