Background: In many gregarious mammals, mothers and offspring have developed the abilities to recognise each other using acoustic signals. Such capacity may develop at different rates after birth/parturition, varying between species and between the participants, i.e., mothers and young. Differences in selective pressures between species, and between mothers and offspring, are likely to drive the timing of the onset of mother-young recognition. We tested the ability of Australian sea lion mothers to identify their offspring by vocalisation, and examined the onset of this behaviour in these females. We hypothesise that a rapid onset of recognition may reflect an adaptation to a colonial lifestyle. Principal Findings: In a playback study maternal responses to own pup and non-filial vocalisations were compared at 12, 24 and every subsequent 24 hours until the females' first departure post-partum. Mothers showed a clear ability to recognise their pup's voice by 48 hours of age. At 24 hours mothers called more, at 48 hours they called sooner and at 72 hours they looked sooner in response to their own pup's vocalisations compared to those of non-filial pups. Conclusions: We demonstrate that Australian sea lion females can vocally identify offspring within two days of birth and before mothers leave to forage post-partum. We suggest that this rapid onset is a result of selection pressures imposed by a colonial lifestyle and may be seen in other colonial vertebrates. This is the first demonstration of the timing of the onset of maternal vocal recognition in a pinniped species.