Decision making is involved in many behaviors contributing to fitness, such as habitat choice, mate selection, and foraging. Because of this, high decision-making accuracy (i.e., selecting the option most beneficial for fitness) should be under strong selection. However, decision making is energetically costly, often involving substantial time and energy to survey the environment to obtain high-quality information. Thus, for high decision making accuracy to evolve, its benefits should outweigh its costs. Inconsistency in the net benefits of decision making across environments is hypothesized to be an important means for maintaining variation in this trait. However, very little is known about how environmental factors influence the evolution of decision making to produce variation among individuals, genotypes, and species. Here, we compared two recently diverged species of Drosophila differing substantially in habitat breadth and degree of environmental predictability and variability: Drosophila sechellia and Drosophila simulans. We found that the species evolving under higher environmental unpredictability and variability showed higher decision-making accuracy, but not higher environmental sampling.