Perceptual learning is a powerful mechanism to enhance perceptual abilities and to form robust memory representations of previously unfamiliar sounds. Memory formation through repeated exposure takes place even for random and complex acoustic patterns devoid of semantic content. The current study sought to scrutinise how perceptual learning of random acoustic patterns is shaped by two potential modulators: temporal regularity of pattern repetition and listeners' attention. To this end, we adapted an established implicit learning paradigm and presented short acoustic sequences that could contain embedded repetitions of a certain sound segment (i.e., pattern) or not. During each experimental block, one repeating pattern recurred across multiple trials, whereas the other patterns were presented in only one trial. During the presentation of sound sequences that contained either temporally regular or jittered within-trial pattern repetitions, participants' attention was directed either towards 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), accompanied by a performance increase in a (within-trial) repetition detection task when listeners attended the sounds. Remarkably, we show a memory-related ERP effect even for the first pattern occurrence per sequence when participants attended the sounds, but not when they were engaged in a visual distractor task. These findings suggest that learning of unfamiliar sound patterns is robust against temporal irregularity and inattention, but attention facilitates access to established memory representations upon first occurrence within a sequence.