A variety of findings suggest that when conducting visual search, we can exploit cues that are statistically related to a target’s location. But is this the result of heuristic mechanisms or an internal model that tracks the statistics of the environment? Here, connections are made between the two explanations, and four models are assessed to probe the mechanisms underlying prediction in search. Participants conducted a simple gaze-contingent search task with five conditions, each of which consists of different combinations of 1st and 2nd order statistics. People’s exploration behaviour adapted to the statistical rules governing target behaviour. Behaviour was most consistent with a model that represents transitions from one location to another, and that makes the underlying assumption that the world is dynamic. This assumption that the world is changeable could not be overridden despite task instruction and nearly 1 h of exposure to unchanging statistics. This means that while people may be suboptimal in some experimental contexts, it may be because their internal mental model makes assumptions that are adaptive in a complex, changeable world.