The capacity of organisms to deal with evolutionary novelty has been regarded by some as a puzzle. If adaptations have been shaped by natural selection operating in the past, then how can they possibly respond adaptively to objects, events, and situations that clearly did not exist until recently? This has been regarded as particularly problematic for adaptationist accounts of human behavior because we are clearly surrounded by many evolutionary novelties, from football to Facebook, that do not cause our brains to seize up in a failure to compute. Traditionally, the answer has been that humans are equipped with more or better general-purpose cognitive capacities than are other animals, though mounting comparative evidence suggests that it is not primarily in the most general mechanisms of cognition that humans and other primates differ. Arguably, progress on the novelty puzzle has been impeded by the lack of adequate theory regarding how adaptations, and in particular psychological adaptations, might be expected to respond to evolutionary novelty. In this talk I describe elements of what such a theory might look like, drawing on prior work in biology, evolutionary psychology, culture-gene coevolution theory, and Bayesian models of cognition, and illustrating the ideas with examples from recent research.