Memory formation has been associated with structural and functional modifications of synapses. Cell adhesion molecules are prominent modulators of synaptic plasticity. Here, we investigated the involvement of the cell adhesion molecules, NCAM, its polysialylated state (PSA-NCAM) and L1 in spatial learning-induced synaptic remodeling and memory storage. A differential regulation of these adhesion molecules was found in the hippocampus of rats submitted to one training session in the spatial, but not cued, version of the Morris water maze. Twenty-four hours after training, synaptic expression of NCAM and PSA-NCAM was increased, whereas L1 appeared markedly decreased. The regulation of these molecules was spatial learning-specific, except for L1 reduction, which could be attributed to swimming under stressful conditions rather than to learning. Subsequent psychopharmacological experiments were performed to address the functional role of NCAM and PSA-NCAM in the formation of spatial memories. Rats received an intracerebroventricular injection of either a synthetic peptide (C3d) aimed to interfere with NCAM function, or endoneuraminidase, an enzyme that cleaves polysialic acid from NCAM. Both treatments affected acquisition of spatial information and lead to impaired spatial memory abilities, supporting a critical role of the observed learning-induced up-regulation of synaptic NCAM expression and polysialylation on spatial learning and memory. Therefore, our findings highlight NCAM as a learning-modulated molecule critically involved in the hippocampal remodeling processes underlying spatial memory formation.