Asymmetric brain function is common across the animal kingdom and involved in language processing, and likely in learning and memory. What regulates asymmetric brain function remains elusive. Here, we show that the nematode Caenorhabditis elegans restructures an asymmetric salt sensing neural circuit during associative learning. Worms memorize and prefer the salt concentration at which they were raised in the presence of food through a left-biased network architecture. When conditioned at elevated salt concentrations, animals change the left-biased to a right-biased network, which explains the changed salt-seeking behavior. The changes in circuit architecture require new synapse formation induced through asymmetric, paracrine insulin-signaling. Therefore, experience-dependent changes in asymmetric network architecture rely on paracrine insulin signaling and are fundamental to learning and behavior.