Although individuals of some species appear able to distinguish among individuals of a second species, an alternative explanation is that individuals of the first species may simply be distinguishing between familiar and unfamiliar individuals of the second species. In that case, they would not be learning unique characteristics of any given heterospecific, as commonly assumed. Here we show that female Northern Mockingbirds (Mimus polyglottos) can quickly learn to distinguish among different familiar humans, flushing sooner from their nest when approached by people who pose increasingly greater threats. These results demonstrate that a common small songbird has surprising cognitive abilities, which likely facilitated its widespread success in human-dominated habitats. More generally, urban wildlife may be more perceptive of differences among humans than previously imagined.