Olfaction is an evolutionary ancient sense, but it remains unclear to what extent it can influence routine human behavior. We examined whether a threat-relevant predator odor (2-methyl-2-thiazoline) would contextually enhance the formation of human fear memory associations. Participants who learned to associate visual stimuli with electric shock in this predator odor context later showed stronger fear responses to the visual stimuli than participants who learned in an aversiveness-matched control odor context. This effect generalized to testing in another odor context, even after extinction training. Results of a separate experiment indicate that a possible biological mechanism for this effect may be increased cortisol levels in a predator odor context. These results suggest that innate olfactory processes can play an important role in human fear learning. Modulatory influences of odor contexts may partly explain the sometimes maladaptive persistence of human fear memory, e.g., in post-traumatic stress disorders.