Where do observers direct their attention in complex scenes? Previous work on the cognitive control of fixation patterns in natural environments suggests that subjects must learn where to direct attention and gaze. We examined this question in the context of a change blindness paradigm, where some objects were more likely to undergo a change in orientation than others. The experiments revealed that observers are capable of learning the frequency with which objects undergo a change, and that this learning is manifested in the distribution of gaze among objects in the scene, as well as in the reaction time for detecting visual changes, and the frequency of localizing changing objects. However, observers were much less sensitive to the conditional probability of a second feature, border color, predicting a change in orientation. We conclude that striking demonstrations of change blindness may reflect not only the constraints of attention and working memory, but also what observers have learnt about what information to attend and select for storage during the task of change detection. Such exploitation of the frequency of change suggests that gaze allocation is sensitive to the probabilistic structure of the environment.