Visual search is faster when a fixed target location is paired with a spatially invariant (vs. randomly changing) distractor configuration, thus indicating that repeated contexts are learned, thereby guiding attention to the target (contextual cueing [CC]). Evidence for memory-guided attention has also been revealed with electrophysiological (electroencephalographic [EEG]) recordings, starting with an enhanced early posterior negativity (N1pc), which signals a preattentive bias toward the target, and, subsequently, attentional and postselective components, such as the posterior contralateral negativity (PCN) and contralateral delay activity (CDA), respectively. Despite effective learning, relearning of previously acquired contexts is inflexible: The CC benefits disappear when the target is relocated to a new position within an otherwise invariant context and corresponding EEG correlates are diminished. The present study tested whether global statistical properties that induce predictions going beyond the immediate invariant layout can facilitate contextual relearning. Global statistical regularities were implemented by presenting repeated and nonrepeated displays in separate streaks (mini blocks) of trials in the relocation phase, with individual displays being presented in a fixed and thus predictable order. Our results revealed a significant CC effect (and an associated modulation of the N1pc, PCN, and CDA components) during initial learning. Critically, the global statistical regularities in the relocation phase also resulted in a reliable CC effect, thus revealing effective relearning with predictive streaks. Moreover, this relearning was reflected in an enhanced PCN amplitude for repeated relative to nonrepeated contexts. Temporally ordered contexts may thus adapt memory-based guidance of attention, particularly the allocation of covert attention in the visual display.