Phenotypic variation is a fundamental prerequisite for cell and organism evolution by natural selection. Whereas the role of stochastic gene expression in phenotypic diversity of genetically identical cells is well studied, not much is known regarding the relationship between stochastic gene expression and individual behavioral variation in animals. We demonstrate that a specific miRNA (miR-466f-3p) is upregulated in the hippocampus of a portion of individual inbred mice upon a Morris water maze task. Significantly, miR-466f-3p positively regulates the neuron morphology, function and spatial learning, and memory capability of mice. Mechanistically, miR-466f-3p represses translation of MEF2A, a negative regulator of learning/memory. Finally, we show that varied upregulation of hippocampal miR-466f-3p results from randomized phosphorylation of hippocampal cyclic AMP (cAMP)-response element binding (CREB) in individuals. This finding of modulation of spatial learning and memory via a randomized hippocampal signaling axis upon neuronal stimulation represents a demonstration of how variation in tissue gene expression lead to varied animal behavior.