Memories of most stimuli in the auditory and other domains are prone to the disruptive interference of intervening events, whereby memory performance continuously declines as the number of intervening events increases. However, melodies in a familiar musical idiom are robust to such interference. We propose that representations of musical structure emerging from syntactic processing may provide partially redundant information that accounts for this robust encoding in memory. The present study employs tonally ambiguous melodies which afford two different syntactic interpretations in the tonal idiom. Crucially, since the melodies are ambiguous, memory across two presentations of the same melody cannot bias whether the interpretation in a second listening will be the same as the first, unless a representation of the first syntactic interpretation is also encoded in memory in addition to sensory information. The melodies were presented in a Memory Task, based on a continuous recognition paradigm, as well as in a Structure Task, where participants reported their syntactic interpretation of each melody following a disambiguating cue. Our results replicate memory-for-melody's robustness to interference, and further establish a predictive relationship between memory performance in the Memory Task and the robustness of syntactic interpretations against the bias introduced by the disambiguating cue in the Structure Task. As a consequence, our results support that a representation based on a disambiguating syntactic parse provides an additional, partially redundant encoding that feeds into memory alongside sensory information. Furthermore, establishing a relationship between memory performance and the formation of structural representations supports the relevance of syntactic relationships towards the experience of music.