Five- to 11-year-olds (N = 91) explored virtual environments with the goal of learning where everything was within the environment (1 trial; Experiment 1) or to find six stars (5 trials/condition; Experiment 2). Participants took part in a standard condition and in an overhead map condition in which they could view their location on a map. In Experiment 1, with increasing age, participants visited more of the environment, had longer path lengths and fewer pauses. In Experiment 2, navigation success (time per target collected) increased with repeated trials and was stronger in the overhead map condition. Associations between exploration behaviour and navigation success demonstrated that fewer pauses, visiting more areas of the environment and stronger target order consistency across trials, were associated with navigation success for both conditions. Additional input was also differentially observed for each condition; age and gender impacted performance in the overhead map condition, whilst the number of revisits impacted performance in the standard condition. Individual difference analysis (Latent Profile Analysis) of the standard condition revealed three profiles. These reflected cautious explorers who were poor at navigating (profile 2), active and efficient explorers who were good at navigating (profile 1) and active and less efficient explorers who were average at navigating (profile 3). This is a first step to understanding exploration behaviour in children and how this relates to navigation success.