Increased cAMP (in dunce mutants) leads to an increase in the structure and function of the Drosophila neuromuscular junction. Synaptic Fasciclin II (Fas II) controls this structural plasticity, but does not alter synaptic function. Here, we show that CREB, the cAMP response element-binding protein, acts in parallel with Fas II to cause an increase in synaptic strength. Expression of the CREB repressor (dCREB2-b) in the dunce mutant blocks functional but not structural plasticity. Expression of the CREB activator (dCREB2-a) increases synaptic strength only in FasII mutants that increase bouton number. This CREB-mediated increase in synaptic strength is due to increased presynaptic transmitter release. Expression of dCREB2-a in a FasII mutant background genetically reconstitutes this cAMP-dependent plasticity. Thus, cAMP initiates parallel changes in CREB and Fas II to achieve long-term synaptic enhancement.