Are young children just random explorers who learn serendipitously? Or are even young children guided by uncertainty-directed sampling, seeking to explore in a systematic fashion? We study how children between the ages of 4 and 9 search in an explore-exploit task with spatially-correlated rewards, where exhaustive exploration is infeasible and not all options can be experienced. By combining behavioral data with a computational model that decomposes search into similarity-based generalization, uncertainty-directed exploration, and random exploration, we map out developmental trajectories of generalization and exploration. The behavioral data show strong developmental differences in children’s capability to exploit environmental structure, with performance and adaptiveness of sampling decisions increasing with age. Through model-based analyses, we disentangle different forms of exploration, finding signatures of both uncertainty-directed and random exploration. The amount of random exploration strongly decreases as children get older, supporting the notion of a developmental ‘cooling off’ process that modulates the randomness in sampling. However, even at the youngest age range, children do not solely rely on random exploration. Even as random exploration begins to taper off, children are actively seeking out options with high uncertainty in a goal-directed fashion, and using inductive inferences to generalize their experience to novel options. Our findings provide critical insights into the behavioral and computational principles underlying the developmental trajectory of learning and exploration.