Predictive processing accounts propose that our brain constantly tries to match top-down internal representations with bottom-up incoming information from the environment. Predictions can lead to prediction errors of varying degrees depending on the extent to which the information encountered in the environment conforms with prior expectations. Theoretical and computational models assume that prediction errors have beneficial effects on learning and memory. However, while there is strong evidence on the effects of prediction error on learning, relatively less evidence is available regarding its effects on memory. Moreover, most of the studies available so far manipulated prediction error by using monetary rewards, whereas in everyday life learning does not always occur in the presence of explicit rewards. We used a task in which participants leaned context/object-category associations of different strength based on the outcomes of their predictions. After learning these associations, participants were presented with trial-unique objects that could match or violate their predictions. Finally, participants were asked to complete a surprise recognition memory test. We used a reinforcement learning model to derive subject-specific trial-to-trial estimates of prediction error at encoding and link it to subsequent recognition memory. Results showed that model-derived prediction errors at encoding influenced subsequent memory as a function of the outcome of participants’ predictions (correct vs incorrect). When participants correctly predicted the object category, stronger prediction errors (as a consequence of weak expectations) led to enhanced memory. In contrast, when participants incorrectly predicted the object category, stronger prediction errors (as a consequence of strong expectations) led to impaired memory. These results reveal a computationally specific influence of prediction error on memory formation, highlighting the important moderating role of choice outcome that may be related to interactions between the hippocampal and striatal dopaminergic systems.