Comparative studies suggest that at least some bird species have evolved mental skills similar to those found in humans and apes. This is indicated by feats such as tool use, episodic-like memory, and the ability to use one's own experience in predicting the behavior of conspecifics. It is, however, not yet clear whether these skills are accompanied by an understanding of the self. In apes, self-directed behavior in response to a mirror has been taken as evidence of self-recognition. We investigated mirror-induced behavior in the magpie, a songbird species from the crow family. As in apes, some individuals behaved in front of the mirror as if they were testing behavioral contingencies. When provided with a mark, magpies showed spontaneous mark-directed behavior. Our findings provide the first evidence of mirror self-recognition in a non-mammalian species. They suggest that essential components of human self-recognition have evolved independently in different vertebrate classes with a separate evolutionary history.