A basic question in cognitive psychology concerns ways in which sensory information is represented in memory. Listeners performed a long-term transposition recognition task in which brief melodies were presented with a chordal context that defined their scale-step interpretations. Context either remained constant or changed at test. In two experiments listeners with moderate amounts of musical experience performed well with constant context but at chance with shifting context. Inexperienced listeners (as well as professionals in one of the studies) performed equally well regardless of context. This result suggests that inexperienced listeners represented melodies as sequences of pitch intervals that remained invariant across context shifts. In contrast, moderately experienced listeners appear to have represented melodies as scale-step sequences that were affected by context. Professionals, while capable of scale-step representation, were able to use a flexible memory-retrieval system to avoid errors with changed context. A third experiment showed that moderately experienced listeners were able to base long-term recognition on either contour or scale-step information, depending on instructions. These results suggest that the scale-step representation used by moderately experienced listeners involved both contour and scale information.