The neural cell adhesion molecule (NCAM) has been implicated in regulating synaptic plasticity mechanisms as well as memory consolidation processes. Attachment of polysialic acid to NCAM (PSA-NCAM) has been reported to down-regulate its adhesive forces, a process hypothesized to be implicated in synapse selection after learning experiences. PSA-NCAM has been critically implicated in hippocampus-related synaptic plasticity and memory storage, but information about its functional role in other brain areas remains scarce. Here, we studied mice deficient for polysialyltransferase-1 (ST8SialV/PST-1), an enzyme which attaches PSA to NCAM during postnatal development and adulthood, and whose deficiency results in a drastic reduction of PSA-NCAM expression throughout the brain in adulthood. Mice were tested for their performance in the water maze and auditory fear conditioning (AFC). We report that ST8SiaIV knockout mice were impaired in spatial as well as reversal learning in the water maze. On the other hand, AFC was intact and ST8SiaIV mice exhibited no impairments in the acquisition or retention of cued fear memories. Spatial orientation learning and reversal learning require complex integration of spatial information and response selection involving the hippocampus and prefrontal cortex, whereas cued fear conditioning is an associative type of emotional memory that highly depends on amygdala function. Therefore, our results indicate that PSA-NCAM contributes differentially to learning processes that differ in the nature of the neural computations involved, which probably reflects a differential role of this molecule in different brain regions.