A visual search task was used to probe how well attention can operate over a dynamically changing visual display. Participants searched for a target item among an array of distractor items while the items either shifted location several times per second or remained stationary. Not surprisingly, Experiment 1 showed that shifting display items slowed search. However, search was faster if the shift preserved the global, configural structure of the display. The results of Experiment 2 suggest that the benefit of maintaining configural structure comes from improved spatial predictability: Knowing where the searchable items will be at any given moment enables faster search. Finally, Experiment 3 shows that, given spatiotemporal continuity, attention can operate just as efficiently over a dynamically changing display as it can over a stationary display. In the real world, objects often move, but they do so in a predictable way. The current findings suggest that the mechanisms underlying search can capitalize on configural predictability and spatiotemporal continuity to enable efficient search in such dynamic situations.