Stimuli encoded shortly before an aversive event are typically well remembered. Traditionally, this emotional memory enhancement has been attributed to beneficial effects of physiological arousal on memory formation. Here, we proposed an additional mechanism and tested whether memory formation is driven by the unpredictable nature of aversive events (i.e., aversive prediction errors). In a combined Pavlovian fear conditioning and incidental memory paradigm, participants saw initially neutral pictures from 2 distinct categories, 1 of which was associated with a risk to receive an electric shock. During encoding, we measured both physiological arousal and explicit prediction errors to explain memory differences in a surprise recognition test that followed approximately 24 hr later. In a first experiment, we show that physiological arousal, expressed as outcome-related skin conductance responses, was associated with improved recognition memory, corroborating arousal-based models. Critically, unsigned binary prediction errors derived from explicit shock expectancy ratings in each trial were also linked to enhanced recognition and model fits showed that the impact of prediction errors on memory was dissociable from the impact of arousal. In a second experiment, we replicated and extended the findings of the first experiment by demonstrating that the memory-promoting effect of prediction errors remained even after controlling for arousal. The present data point to prediction error-related learning as a cognitive mechanism that contributes to the emotional enhancement of memory, above and beyond the well-established effects of arousal in emotional memory formation.