Good decisions require information. When people face a situation in which they need to make a choice but know little about the options available, how do they search for information? We present an analysis of over 1,000,000 information-search decisions made by over 2,500 individuals in a decisions-from-experience setting. We found that individuals solve the problem in a smart way, relying on several strategies—including two novel ones. In discovery-driven search, people leverage detailed knowledge about the structure of the environment to find previously unobserved outcomes and terminate information search after all possible outcomes have been observed. In fixed search, on the other hand, people decide in advance how much information they want to obtain and stick to that decision irrespective of the feedback obtained. These novel strategies are distinct from uncertainty-driven search—the dominant strategy in research on information search—in which people engaged only after all outcomes had been observed. Overall, our results suggest that people adaptively and dynamically rely on a toolbox of information-search strategies. This is at odds with a narrow interpretation of information search as cost–benefit optimization and highlights a need for broader theories of information-search behavior in decisions under uncertainty, capturing the diversity of the strategic tools recruited.