Many previous studies have shown that arousal affects time perception, suggesting a direct influence of arousal on the speed of the pacemaker of the internal clock. However, it is unknown whether arousal influences the mental representation of tempo (speed) for highly familiar and complex stimuli, such as well-known melodies, that have long-term representations in memory. Previous research suggests that mental representations of the tempo of familiar melodies are stable over time; the aim of the present study was to investigate whether these representations can be systematically altered via an increase in physiological arousal. Participants adjusted the tempo of 14 familiar melodies in real time until they found a tempo that matched their internal representation of the appropriate tempo for that piece. The task was carried out before and after a physiologically arousing (exercise) or nonarousing (anagrams) manipulation. Participants completed this task both while hearing the melodies aloud and while imagining them. Chosen tempi increased significantly following exercise-induced arousal, regardless of whether a melody was heard aloud or imagined. These findings suggest that a change in internal clock speed affects temporal judgments even for highly familiar and complex stimuli such as music.