To understand auditory scenes, listeners track and retain the statistics of sensory inputs as they unfold over time. We combined behavioural manipulation and modelling to investigate how sequence statistics are encoded into long-term memory and used to interpret incoming sensory signals. In a series of experiments, participants detected the emergence of regularly repeating patterns in novel rapid sound sequences. Unbeknownst to them, a few regular patterns reoccurred sparsely (every ∼3 minutes). Reoccurring sequences showed a rapidly growing detection time advantage over novel sequences. This effect was implicit, robust to interference, and persisted up to 7 weeks. Human performance was reproduced by a memory-constrained probabilistic model, where sequences are stored as n-grams and are subject to memory decay. Results suggest that similar psychological mechanisms may underlie integration processes over different-time scales in memory formation and flexible retrieval.