The neural cell adhesion molecule 1 (NCAM-1) has been implicated in several brain-related biological processes, including neuronal migration, axonal branching, fasciculation, and synaptogenesis, with a pivotal role in synaptic plasticity. Here, we investigated the evolutionary conserved role of NCAM-1 in learning and memory. First, we investigated sustained changes in ncam-1 expression following aversive olfactory conditioning in C. elegans using molecular genetic methods. Furthermore, we examined the link between epigenetic signatures of the NCAM1 gene and memory in two human samples of healthy individuals (N = 568 and N = 319) and in two samples of traumatized individuals (N = 350 and N = 463). We found that olfactory conditioning in C. elegans induced ncam-1 expression and that loss of ncam-1 function selectively impaired associative long-term memory, without causing acquisition, sensory, or short-term memory deficits. Reintroduction of the C. elegans or human NCAM1 fully rescued memory impairment, suggesting a conserved role of NCAM1 for memory. In parallel, DNA methylation of the NCAM1 promoter in two independent healthy Swiss cohorts was associated with memory performance. In two independent Sub-Saharan populations of conflict zone survivors who had faced severe trauma, DNA methylation at an alternative promoter of the NCAM1 gene was associated with traumatic memories. Our results support a role of NCAM1 in associative memory in nematodes and humans, and might, ultimately, be helpful in elucidating diagnostic markers or suggest novel therapy targets for memory-related disorders, like PTSD.