Music is a cultural universal, yet the individual experience of music can strongly differ between listeners. Here, we investigate the similarity of listeners’ response patterns in the context of memory for melody and argue that memory can serve as a proxy to perception. If music perception is similar across listeners, then this similarity should be reflected in similar memory response patterns toward a specific melody corpus. We used interrater agreement in melody recognition tasks as a window into how “similarly” listeners perceive music, and melodies in particular. Specifically, the data of 10 published melody recognition experiments were reanalyzed and findings indicate interrater agreement of up to r = .70. However, interrater agreement was strongly dependent on whether explicit recognition or indirect recognition in the form of perceived familiarity was measured, with explicit recognition showing higher agreement among listeners. Furthermore, the specific melody corpus and tuning system played a significant role, as did whether melodies consisted of pitch-only, rhythm-only, or both pitch and rhythm information. Results are interpreted in light of their practical implications for computational models of memory for melody. We argue that these findings provide strong evidence that mathematical models designed to predict human memory for melody should focus on musical features that combine rather than separate components of rhythm and melody, and with greater emphasis on musical features that are independent of the tuning system.