A striking neuronal connectivity change in C. elegans involves the coordinated elimination of existing synapses and formation of synapses at new locations, without altering neuronal morphology. Here, we investigate the tripartite interaction between dynamic microtubules (MTs), kinesin-1, and vesicular cargo during this synapse remodeling. We find that a reduction in the dynamic MT population in motor neuron axons, resulting from genetic interaction between loss of function in the conserved MAPKKK dlk-1 and an α-tubulin mutation, specifically blocks synapse remodeling. Using live imaging and pharmacological modulation of the MT cytoskeleton, we show that dynamic MTs are increased at the onset of remodeling and are critical for new synapse formation. DLK-1 acts during synapse remodeling, and its function involves MT catastrophe factors including kinesin-13/KLP-7 and spastin/SPAS-1. Through a forward genetic screen, we identify gain-of-function mutations in kinesin-1 that can compensate for reduced dynamic MTs to promote synaptic vesicle transport during remodeling. Our data provide in vivo evidence supporting the requirement of dynamic MTs for kinesin-1-dependent axonal transport and shed light on the role of the MT cytoskeleton in facilitating neural circuit plasticity.