Foraging animals continually face the decision of whether to exploit known resources or explore for new ones, a decision with large implications for their fitness. Though animal foraging decisions have been extensively studied, we currently lack a deep understanding of how the exploitation-exploration trade-off has evolved, including how it is shaped by divergent selection pressures between species. As a first step towards examining how the exploitation-exploration trade-off has been adaptively tuned by natural selection, we compared the exploratory behavior of four honey bee species that differ in traits such as nest architecture, body size, and colony size. In a common behavioral context—exploratory behavior triggered by a decrease in quality of a known food resource—we found species differences in exploratory behavior that are consistent with selection arising from evolved differences in nest architecture, though the behavioral differences were also strongly influenced by the magnitude of the reward decrease. We had expected that species that build their nests in the open, and hence face a higher fitness cost of worker attrition compared with species that inhabit protective cavities, would be less likely to prolong unrewarded search when food declines in quality. The behavioral data were partially consistent with this expectation. However, at times, the environmental context strongly modulated species differences in behavior that would be expected based on nest architecture. Overall, our results suggest that the resolution of the exploitation-exploration trade-off has been adaptively tuned between species by a number of interacting selection pressures.