Gap junctions play an important role in the regulation of neuronal metabolism and homeostasis by serving as connections that enable small molecules to pass between cells and synchronize activity between cells. Although recent studies have linked gap junctions to memory formation, it remains unclear how they contribute to this process. Gap junctions are hexameric hemichannels formed from the connexin and pannexin gene families in chordates and the innexin (inx) gene family in invertebrates. Here we show that two modulatory neurons, the anterior paired lateral (APL) neuron and the dorsal paired medial (DPM) neuron, form heterotypic gap junctions within the mushroom body (MB), a learning and memory center in the Drosophila brain. Using RNA interference-mediated knockdowns of inx7 and inx6 in the APL and DPM neurons, respectively, we found that flies showed normal olfactory associative learning and intact anesthesia-resistant memory (ARM) but failed to form anesthesia-sensitive memory (ASM). Our results reveal that the heterotypic gap junctions between the APL and DPM neurons are an essential part of the MB circuitry for memory formation, potentially constituting a recurrent neural network to stabilize ASM.