We investigated the effects of familiarity, level of musical expertise, musical tempo, and structural boundaries on the identification of familiar and unfamiliar tunes. Healthy Western listeners (N = 62; age range 14–64 years) judged their level of familiarity with a preselected set of melodies when the number of tones of a given melody was increased from trial to trial according to the so-called gating paradigm. The number of tones served as one dependent measure. The second dependent measure was the physical duration of the stimulus presentation until listeners identified a melody as familiar or unfamiliar. Results corroborate previous work, suggesting that listeners need less information to recognize familiar as compared to unfamiliar melodies. Both decreasing and increasing the original tempo by a factor of two delayed the identification of familiar melodies. Furthermore, listeners had more difficulty identifying unfamiliar melodies when tempo was increased. Finally, musical expertise significantly influenced identification of either melodic category, i.e., reducing the required number of tones. Taken together, the findings support theories which suggest that tempo information is coded in melody representation, and that musical expertise is associated with especially efficient strategies for accessing long-term representations of melodic materials.