Theoretical and modeling studies demonstrate that heterosynaptic plasticity-changes at synapses inactive during induction-facilitates fine-grained discriminative learning in Hebbian-type systems, and helps to achieve a robust ability for repetitive learning. A dearth of tools for selective manipulation has hindered experimental analysis of the proposed role of heterosynaptic plasticity in behavior. Here we circumvent this obstacle by testing specific predictions about the behavioral consequences of the impairment of heterosynaptic plasticity by experimental manipulations to adenosine A1 receptors (A1Rs). Our prior work demonstrated that the blockade of adenosine A1 receptors impairs heterosynaptic plasticity in brain slices and, when implemented in computer models, selectively impairs repetitive learning on sequential tasks. Based on this work, we predict that A1R knock-out (KO) mice will express (1) impairment of heterosynaptic plasticity and (2) behavioral deficits in learning on sequential tasks. Using electrophysiological experiments in slices and behavioral testing of animals of both sexes, we show that, compared with wild-type controls, A1R KO mice have impaired synaptic plasticity in visual cortex neurons, coupled with significant deficits in visual discrimination learning. Deficits in A1R knockouts were seen specifically during relearning, becoming progressively more apparent with learning on sequential visual discrimination tasks of increasing complexity. These behavioral results confirm our model predictions and provide the first experimental evidence for a proposed role of heterosynaptic plasticity in organism-level learning. Moreover, these results identify heterosynaptic plasticity as a new potential target for interventions that may help to enhance new learning on a background of existing memories. Understanding how interacting forms of synaptic plasticity mediate learning is fundamental for neuroscience. Theory and modeling revealed that, in addition to Hebbian-type associative plasticity, heterosynaptic changes at synapses that were not active during induction are necessary for stable system operation and fine-grained discrimination learning. However, lacking tools for selective manipulation prevented behavioral analysis of heterosynaptic plasticity. Here we circumvent this barrier: from our prior experimental and computational work we predict differential behavioral consequences of the impairment of Hebbian-type versus heterosynaptic plasticity. We show that, in adenosine A1 receptor knock-out mice, impaired synaptic plasticity in visual cortex neurons is coupled with specific deficits in learning sequential, increasingly complex visual discrimination tasks. This provides the first evidence linking heterosynaptic plasticity to organism-level learning.