Much of contemporary associative learning research is focused on understanding how and when the associative history of cues affects later learning about those cues. Very little work has investigated the effects of the associative history of outcomes on human learning. Three experiments extended the “learned irrelevance” paradigm from the animal conditioning literature to examine the influence of an outcome’s prior predictability on subsequent learning of relationships between cues and that outcome. All 3 experiments found evidence for the idea that learning is biased by the prior predictability of the outcome. Previously predictable outcomes were readily associated with novel predictive cues, whereas previously unpredictable outcomes were more readily associated with novel nonpredictive cues. This finding highlights the importance of considering the associative history of outcomes, as well as cues, when interpreting multistage designs. Associative and cognitive explanations of this certainty matching effect are discussed.