Animals have a remarkable ability to track dynamic sensory information. For example, the nematode Caenorhabditis elegans can locate a diacetyl odor source across a 100,000-fold concentration range. Here, we relate neuronal properties, circuit implementation, and behavioral strategies underlying this robust navigation. Diacetyl responses in AWA olfactory neurons are concentration and history dependent; AWA integrates over time at low odor concentrations, but as concentrations rise, it desensitizes rapidly through a process requiring cilia transport. After desensitization, AWA retains sensitivity to small odor increases. The downstream AIA interneuron amplifies weak odor inputs and desensitizes further, resulting in a stereotyped response to odor increases over three orders of magnitude. The AWA-AIA circuit drives asymmetric behavioral responses to odor increases that facilitate gradient climbing. The adaptation-based circuit motif embodied by AWA and AIA shares computational properties with bacterial chemotaxis and the vertebrate retina, each providing a solution for maintaining sensitivity across a dynamic range.