Animals with complex nervous systems demand sleep for memory consolidation and synaptic remodeling. Here we show that though the Caenorhabditis elegans nervous system has a limited number of neurons and connections, sleep is necessary for both processes. In addition, it is unclear in any system if sleep collaborates with experience to change synaptic connections between specific neurons and whether this ultimately affects behavior. C. elegans neurons have defined synaptic connections and well-described contributions to specific behaviors. We show that spaced odor-training induces long-term memory, and sleep after training is required for long-term memory. Memory consolidation, but not acquisition, requires a pair of interneurons, the AIYs, which play a role in odor-seeking behavior. In worms that have consolidated memory, both sleep and odor conditioning are required to diminish inhibitory synaptic connections between the AWC chemosensory neurons and the AIY interneurons. Thus, we demonstrate in a living organism that sleep is required for events immediately after training that drive memory consolidation and alter synaptic structures.