An animal's ability to recognize another individual by matching their image to their voice suggests they form internal representations of other individuals. To what extent this ability, termed cross-modal individual recognition, extends to birds other than corvids is unknown. Here, we used an expectancy violation paradigm to determine whether a monogamous territorial seabird (Spheniscus demersus) can cross-modally recognize familiar conspecifics (partners or colony-mates). After pairs of penguins spent time together in an isolated area, one of the penguins was released from the area leaving the focal penguin alone. Subsequently, we played contact calls of the released penguin (congruent condition) or a different penguin (incongruent condition). After being paired with a colony-mate, focal penguins' response latency to the auditory stimulus was faster in the incongruent compared to congruent condition, indicating the mismatch violated their expectations. This behavioural pattern was not observed in focal penguins after being paired with their partner. We discuss these different results in the light of penguins’ natural behaviour and the evolution of social communication strategies. Our results suggest that cross-modal individual recognition extends to penguins and reveals, in contrast with previously thought, that social communication between members of this endangered species can also use visual cues.