Sleep, in particular REM sleep, has been shown to improve the consolidation of emotional memories. Here, we investigated the role of sleep and sleep deprivation on the consolidation of fear memories and underlying neuronal mechanisms. We employed a Pavlovian fear conditioning paradigm either followed by a night of polysomnographically monitored sleep, or wakefulness in forty healthy participants. Recall of learned fear was better after sleep, as indicated by stronger explicitly perceived anxiety and autonomous nervous responses. These effects were positively correlated with the preceding time spent in REM sleep and paralleled by activation of the basolateral amygdala. These findings suggest REM sleep-associated consolidation of fear memory in the human amygdala. In view of the critical participation of fear learning mechanisms in the etiology of anxiety and post-traumatic stress disorder, deprivation of REM sleep after exposure to distressing events is an interesting target for further investigation.