A basic function of cognition is to detect regularities in sensory input to facilitate the prediction and recognition of future events. It has been proposed that these implicit expectations arise from an internal predictive coding model, based on knowledge acquired through processes such as statistical learning, but it is unclear how different types of statistical information affect listeners’ memory for auditory stimuli. We used a combination of behavioral and computational methods to investigate memory for non‐linguistic auditory sequences. Participants repeatedly heard tone sequences varying systematically in their information‐theoretic properties. Expectedness ratings of tones were collected during three listening sessions, and a recognition memory test was given after each session. Information‐theoretic measures of sequential predictability significantly influenced listeners’ expectedness ratings, and variations in these properties had a significant impact on memory performance. Predictable sequences yielded increasingly better memory performance with increasing exposure. Computational simulations using a probabilistic model of auditory expectation suggest that listeners dynamically formed a new, and increasingly accurate, implicit cognitive model of the information‐theoretic structure of the sequences throughout the experimental session.