When listening to music, we form implicit expectations about the forthcoming temporal sequence. Listeners acquire knowledge of music through processes such as statistical learning, but how do different types of statistical information affect listeners’ learning and memory? To investigate this, we conducted a behavioral study in which participants repeatedly heard tone sequences varying within a range of information-theoretic measures. Expectedness ratings of tones were collected during three listening sessions, and a recognition memory test was given after each session. This enabled us to examine how statistical information affects expectation and memory for tone sequences over a period of increasing exposure. We found significant correlations between listeners’ expectedness ratings and measures of information theory (IT), and although listeners demonstrated poor overall memory performance, the IT properties significantly impacted on musical memory. Generally, simple sequences yielded increasingly better memory performance. High-information sequences, for which making accurate predictions is difficult, resulted in consistently poor recognition memory.