Perceptually salient non-targets typically interfere with target processing, but such disruption can be mitigated by top-down knowledge that the salient item is not task-relevant (Geng and DiQuattro, 2010). This exploitation of statistical knowledge optimizes behavior and is thought to be underwritten by locus coeruleus – norepinephrine (LC-NE) innervation from neurons in the frontal cortex (Aston-Jones and Cohen, 2005; Minzenberg et al., 2009). The two different modes of LC neuronal firing (i.e., tonic and phasic) are correlated with changes in pupil size, and the shift between these two population conditions mediates the tradeoff between behavioral exploration and exploitation (Gilzenrat et al., 2010). In this study, we investigated the relationship between pupil size and performance on a visual search task in which the probability of the target being perceptually salient was manipulated from block-to-block. Our results demonstrate that when the probability changes (e.g., the ratio of salient target to salient distracters increased from 0:100 to 30:70 to 70:30 to 100:0), a period of uncertainty ensues in which behavior is more variable and the prestimulus pupil diameter increases in size. This suggests that subjects were engaged in exploration of the task statistics during block transitions, but subsequently began to exploit the current paradigm as the new salience probabilities were learned. These results are consistent with the idea that the LC-NE system underlies the tendency to explore or exploit knowledge about environmental structure, and that pupil diameter is a viable measure of perceived task-related uncertainty that influences the strategic allocation of spatial attention.