Novel motor skills are learned through repetitive practice and, once acquired, persist long after training stops. Earlier studies have shown that such learning induces an increase in the efficacy of synapses in the primary motor cortex, the persistence of which is associated with retention of the task. However, how motor learning affects neuronal circuitry at the level of individual synapses and how long-lasting memory is structurally encoded in the intact brain remain unknown. Here we show that synaptic connections in the living mouse brain rapidly respond to motor-skill learning and permanently rewire. Training in a forelimb reaching task leads to rapid (within an hour) formation of postsynaptic dendritic spines on the output pyramidal neurons in the contralateral motor cortex. Although selective elimination of spines that existed before training gradually returns the overall spine density back to the original level, the new spines induced during learning are preferentially stabilized during subsequent training and endure long after training stops. Furthermore, we show that different motor skills are encoded by different sets of synapses. Practice of novel, but not previously learned, tasks further promotes dendritic spine formation in adulthood. Our findings reveal that rapid, but long-lasting, synaptic reorganization is closely associated with motor learning. The data also suggest that stabilized neuronal connections are the foundation of durable motor memory.