We investigate whether a spatial representation of a search task supports 4- to 7-year-old children’s information-search strategies, relative to their performance in a question-asking game. In Experiment 1, children played two computationally and structurally analogous search games: a spatial search task, the maze-exploration game, in which they had to discover the path through a maze, and a verbal search task, the 20-questions game, where they had to identify a target monster from a set of eight monsters by asking yes-no questions. We found that children made more informative queries in the maze-exploration game than in the 20-questions game. Children’s performance in the 20-questions game improved with age, whereas there were no age-related differences in the spatial task. In Experiment 2, we introduced a non-verbal version of the 20-questions game, in which children had to select which features to query (e.g., color) in order to identify the target monster. We found that children performed equally well in both tasks, with no age-related performance differences. Our results demonstrate that efficient search strategies emerge much earlier than previously assumed, suggesting that young children’s difficulties in the 20-questions game are directly related to the verbal requirements of the task. These findings highlight the importance of developing age-appropriate paradigms that capture children’s early competence, in order to gain a more comprehensive picture of their emerging information-search abilities.