Studies of kin recognition in birds have largely focused on parent-offspring recognition using auditory or visual discrimination. Recent studies indicate that birds use odors during social and familial interactions and possibly for mate choice, suggesting olfactory cues may mediate kin recognition as well. Here, we show that Humboldt penguins (Spheniscus humboldti), a natally philopatric species with lifetime monogamy, discriminate between familiar and unfamiliar non-kin odors (using prior association) and between unfamiliar kin and non-kin odors (using phenotype matching). Penguins preferred familiar non-kin odors, which may be associated with the recognition of nest mates and colony mates and with locating burrows at night after foraging. In tests of kin recognition, penguins preferred unfamiliar non-kin odors. Penguins may have perceived non-kin odors as novel because they did not match the birds' recognition templates. Phenotype matching is likely the primary mechanism for kin recognition within the colony to avoid inbreeding. To our knowledge this is the first study to provide evidence of odor-based kin discrimination in a bird.