In repeated visual search tasks, facilitation of reaction times (RTs) due to repetition of the spatial arrangement of items occurs independently of RT facilitation due to improvements in general task performance. Whereas the latter represents typical procedural learning, the former is a kind of implicit memory that depends on the medial temporal lobe (MTL) memory system and is impaired in patients with amnesia. A third type of memory that develops during visual search is the observers’ explicit knowledge of repeated displays. Here, we used a visual search task to investigate whether procedural memory, implicit contextual cueing, and explicit knowledge of repeated configurations, which all arise independently from the same set of stimuli, are influenced by sleep. Observers participated in two experimental sessions, separated by either a nap or a controlled rest period. In each of the two sessions, they performed a visual search task in combination with an explicit recognition task. We found that (1) across sessions, MTL-independent procedural learning was more pronounced for the nap than rest group. This confirms earlier findings, albeit from different motor and perceptual tasks, showing that procedural memory can benefit from sleep. (2) Likewise, the sleep group compared with the rest group showed enhanced context-dependent configural learning in the second session. This is a novel finding, indicating that the MTL-dependent, implicit memory underlying contextual cueing is also sleep-dependent. (3) By contrast, sleep and wake groups displayed equivalent improvements in explicit recognition memory in the second session. Overall, the current study shows that sleep affects MTL-dependent as well as MTL-independent memory, but it affects different, albeit simultaneously acquired, forms of MTL-dependent memory differentially.