During sleep, humans can strengthen previously acquired memories, but whether they can acquire entirely new information remains unknown. The nonverbal nature of the olfactory sniff response, in which pleasant odors drive stronger sniffs and unpleasant odors drive weaker sniffs, allowed us to test learning in humans during sleep. Using partial-reinforcement trace conditioning, we paired pleasant and unpleasant odors with different tones during sleep and then measured the sniff response to tones alone during the same nights' sleep and during ensuing wake. We found that sleeping subjects learned novel associations between tones and odors such that they then sniffed in response to tones alone. Moreover, these newly learned tone-induced sniffs differed according to the odor pleasantness that was previously associated with the tone during sleep. This acquired behavior persisted throughout the night and into ensuing wake, without later awareness of the learning process. Thus, humans learned new information during sleep.