The extent to which behavior is shaped by experience varies between individuals. Genetic differences contribute to this variation, but the neural mechanisms are not understood. Here, we dissect natural variation in the behavioral flexibility of two Caenorhabditis elegans wild strains. In one strain, a memory of exposure to 21% O2 suppresses CO2-evoked locomotory arousal; in the other, CO2 evokes arousal regardless of previous O2 experience. We map that variation to a polymorphic dendritic scaffold protein, ARCP-1, expressed in sensory neurons. ARCP-1 binds the Ca2+-dependent phosphodiesterase PDE-1 and co-localizes PDE-1 with molecular sensors for CO2 at dendritic ends. Reducing ARCP-1 or PDE-1 activity promotes CO2 escape by altering neuropeptide expression in the BAG CO2 sensors. Variation in ARCP-1 alters behavioral plasticity in multiple paradigms. Our findings are reminiscent of genetic accommodation, an evolutionary process by which phenotypic flexibility in response to environmental variation is reset by genetic change.