Past research in animals has suggested that attention is distributed to exploit known relationships between stimuli (e.g., Mackintosh, 1975) and explore stimuli whose consequences are uncertain (e.g., Pearce & Hall, 1980). The resulting changes in attention influence how animals learn new information involving those stimuli. While there is strong support for exploitative attention and its effects on learning in humans, the evidence for exploratory attention is less well developed. Two experiments examined whether preferential allocation of attention (as measured by eye-gaze) to cues associated with uncertainty leads to more rapid learning of new associations involving these cues in the future. In each experiment, participants first learned about compounds containing one predictive cue and one non-predictive cue. The level of uncertainty during this first stage of training was also manipulated: cue-outcome relationships were either deterministic (certain) or probabilistic (uncertain). In a second stage, new cue-outcome relationships were trained and the uncertainty of these relationships could be resolved by learning about the previously non-predictive cues. As a result of the manipulation of uncertainty in the first stage, some participants experienced a sudden onset of uncertainty at the start of this second stage, while others experienced a stable level of uncertainty throughout the experiment. Experiment 1 showed that participants who experienced an onset of uncertainty learned novel cue-outcome associations faster than participants for whom uncertainty was constant. Furthermore, participants experiencing unexpected uncertainty showed a greater increase in attention to cues in Stage 2. When the first stage of training was extended in Experiment 2 a larger difference in the rate of learning between the two conditions was observed in the second stage. We argue that this represents evidence for an effect of exploratory attention on rate of learning in humans.