Expression of the neural cell adhesion molecule (NCAM) has been shown to promote long-term potentiation (LTP) and stabilization of synapses during early synaptogenesis. Here, we searched for the mechanisms of synaptogenic activity of NCAM, focusing on the role of polysialic acid (PSA), an unusual carbohydrate preferentially associated with NCAM. We show that enzymatic removal of PSA with endoneuraminidase-N (endo-N) abolished preferential formation of synapses on NCAM-expressing cells in heterogenotypic cocultures of wild-type and NCAM-deficient hippocampal neurons. Transfection of NCAM-deficient neurons with either of three major NCAM isoforms (different in intracellular domains but identical in extracellular domains and carrying PSA) stimulated preferential synapse formation on NCAM isoform-expressing neurons. Enzymatic removal of heparan sulfates from cultured neurons and a mutation in the heparin-binding domain of NCAM diminished synaptogenic activity of neuronally expressed PSA-NCAM, suggesting that interaction of NCAM with heparan sulfate proteoglycans mediates this activity. PSA-NCAM-driven synaptogenesis was also blocked by antagonists to fibroblast growth factor receptor and NMDA subtype of glutamate receptors but not by blockers of non-NMDA glutamate receptors and voltage-dependent Na+ channels. Enzymatic removal of PSA and heparan sulfates also blocked the increase in the number of perforated spine synapses associated with NMDA receptor-dependent LTP in the CA1 region of organotypic hippocampal cultures. Thus, neuronal PSA-NCAM in complex with heparan sulfate proteoglycans promotes synaptogenesis and activity-dependent remodeling of synapses.