The evolutionary origin of rhythm perception, a cognitive ability essential to musicality, remains unresolved [1-5]. The ability to perceive and memorize rhythmic sounds is widely shared among humans [6] but seems rare among other mammals [7, 8]. Although the perception of temporal metrical patterns has been found in a few species, this ability has only been demonstrated through behavioral training [9] (but see [10] for an example of spontaneous tempo coordination in a bonobo), and there is no experimental evidence to indicate its biological function. Furthermore, there is no example of a non-human mammal able to remember and recognize auditory rhythmic patterns among a wide range of tempi. In the northern elephant seal Mirounga angustirostris, the calls of mature males comprise a rhythmic series of pulses, with the call of each individual characterized by its tempo and timbre; these individual vocal signatures are stable over years and across contexts [11]. Here, we report that northern elephant seal males routinely memorize and recognize the unique tempo and timbre of their rivals' voices and use this rhythmic information to individually identify competitors, which facilitates navigation within the social network of the rookery. By performing playbacks with natural and modified vocalizations, we show that males are sensitive to call rhythm disruption independently of modification of spectral features and that they use both temporal and spectral cues to identify familiar rivals. While spectral features of calls typically encode individual identity in mammalian vocalizations [12], this is the first example of this phenomenon involving sound rhythm.