Abstract Learning from examples and adapting to new circumstances are fundamental attributes of human cognition. However, it is unclear what conditions allow for fast and successful learning, especially in nonhuman subjects. To determine how rapidly freely moving mice can learn a new discrimination criterion (DC), we design a two-alternative forced-choice visual discrimination paradigm in which the DCs governing the task can change between sessions. We find that experienced animals can learn a new DC after being exposed to only five training and three testing trials. The propensity for single session learning improves over time and is accurately predicted based on animal experience and criterion difficulty. After establishing the procedural learning of a paradigm, mice continuously improve their performance in new circumstances. Thus, mice learn to learn.