According to the synaptic trace theory of memory, activity-induced changes in the pattern of synaptic connections underlie the storage of information for long periods. In this framework, the stability of memory critically depends on the stability of the underlying synaptic connections. Surprisingly however, synaptic connections in the living brain are highly volatile, which poses a fundamental challenge to the synaptic trace theory. Here we review recent experimental evidence that link the initial formation of a memory with changes in the pattern of connectivity, but also evidence that synaptic connections are considerably volatile even in the absence of learning. Then we consider different theoretical models that have been put forward to explain how memory can be maintained with such volatile building blocks.