The formation of memory representations for novel sounds often relies on implicit perceptual learning. Memories are formed through repeated exposure, and successful learning facilitates perception. Such perceptual learning takes place even for random, complex acoustic patterns devoid of semantic content. However, less is known about whether memory formation is modulated by different features of the learning context. The current study explored the influence of two contextual factors: temporal regularity of pattern recurrence and listeners’ attention. We adapted an established implicit learning paradigm in which listeners typically become better in detecting pattern repetitions embedded in random acoustic sequences for patterns that recur across multiple trials compared to non-recurring patterns presented in only one trial. Here we presented listeners with random acoustic sequences that contained temporally regular or jittered repetitions of sound patterns. During sound presentation, their attention was directed towards the acoustic pattern repetitions or away from the auditory stimulation. Overall, we found a memory-related modulation of the event-related potential (ERP) and an increase in inter-trial phase coherence for patterns that recurred across multiple trials (compared to non-recurring patterns). Remarkably, a memory-related ERP effect was present even for the first pattern occurrence per sequence when participants attended to the sounds, but not when they were engaged in a visual distractor task. These findings suggest that memory formation for unfamiliar sound patterns is robust against temporal irregularity and in-attention, but attention facilitates access to established memory representations for previously presented patterns upon first occurrence within a sequence.