SUMMARY 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, sleep is necessary for both processes. In addition, it is unclear in any system if sleep collaborates with experience to alter synapses between specific neurons and whether this ultimately affects behavior. C. elegans neurons have defined connections and well-described contributions to behavior. We show that spaced odor-training and post-training sleep induce 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 consolidate memory, both sleep and odor conditioning are required to diminish inhibitory synaptic connections between the AWC chemosensory neurons and the AIYs. Thus, we demonstrate in a living organism that sleep is required for events immediately after training that drive memory consolidation and alter synaptic structures.