Why do animals learn to perform some behaviors while others are innate? Why do animals learn some things more easily than others? And, why do animals remember some things better than others? Theoreticians argue that patterns of environmental change explain these patterns, but we have little data to support these claims. I used statistical decision theory to model behaviors and fitness consequences, and experimental evolution studies with fruit flies where I manipulated patterns of environmental change across evolutionary time, to address the first two of these fundamental questions about the evolution of learning. The first experiment tested the effects of the reliability of experience and the fixity of the best action upon the evolution of learning and non-learning across 30 generations. I found that indeed, the interaction of these two variables determined when learning, and when non-learning evolved. The second study was a full factorial experiment manipulating the reliabilities of two modes of stimuli: olfactory and visual. After 40 generations, I found that as predicted, flies in environments where olfactory stimuli are reliable learned better about olfactory than color stimuli, with the same being true for color stimuli. Finally, I addressed the question of why animals remember some things better than others using a dynamic programming technique and experiment with blue jays, finding interactions between rates of change and time. These novel studies show the importance of reliability and change in evolution of learning and memory.