Our ability to make predictions and monitor regularities has a profound impact on the way we perceive the environment, but the effect this mechanism has on memory is not well understood. In four experiments, we explored the effects on memory of the expectation status of information at encoding or at retrieval. In a rule-learning task participants learned a contingency relationship between 6 different symbols and the type of stimulus that followed each one. Either at encoding (Experiments 1a and 1b) or at retrieval (Experiments 2a and 2b), the established relationship was violated for a subset of stimuli resulting in the presentation of both expected and unexpected stimuli. The expectation status of the stimuli was found to have opposite effects on familiarity and recollection performance, the two kinds of memory that support recognition memory. At encoding (Experiments 1a and 1b), the presentation of expected stimuli selectively enhanced subsequent familiarity performance, while unexpected stimuli selectively enhanced subsequent recollection. Similarly, at retrieval (Experiments 2a and 2b), expected stimuli were more likely to be deemed familiar than unexpected stimuli, whereas unexpected stimuli were more likely to be recollected than were expected stimuli. These findings suggest that two separate memory enhancement mechanisms exist; one sensitive and modulating the accuracy of memory for the contextually distinctive or unexpected, and the other sensitive to and modulating the accuracy of memory for the expected. Therefore, the degree to which information fits with expectation has critical implications for the type of computational mechanism that will be engaged to support memory.