Music in a minor key is often claimed to sound sad, whereas music in a major key is typically viewed as sounding cheerful. Such claims suggest that maintaining or switching the tonality of a musical selection between information encoding and retrieval should promote robust “mood-mediated” context-dependent memory (CDM) effects. The reported experiment examined this hypothesis using versions of a Chopin waltz where the key was either reinstated or switched at retrieval, so producing minor- -minor, major--major, minor--major and major--minor conditions. Better word recall arose in reinstated-key conditions (particularly for the minor--minor group) than in switched-key conditions, supporting the existence of tonality-based CDM effects. The tonalities also induced different mood states. The minor key induced a more negative mood than the major key, and participants in switched-key conditions demonstrated switched moods between learning and recall. Despite the association between music tonality and mood, a path analysis failed to reveal a reliable mood-mediation effect. We discuss why mood-mediated CDM may have failed to emerge in this study, whilst also acknowledging that an alternative “mental-context” account can explain our results (i.e., the mental representation of music tonality may act as a contextual cue that elicits information retrieval).