The ability of animals to effectively locate and navigate toward food sources is central for survival. Here, using C. elegans nematodes, we reveal the neural mechanism underlying efficient navigation in chemical gradients. This mechanism relies on the activity of two types of chemosensory neurons: one (AWA) coding gradients via stochastic pulsatile dynamics, and the second (AWCON) coding the gradients deterministically in a graded manner. The pulsatile dynamics of the AWA neuron adapts to the magnitude of the gradient derivative, allowing animals to take trajectories better oriented toward the target. The robust response of AWCON to negative derivatives promotes immediate turns, thus alleviating the costs incurred by erroneous turns dictated by the AWA neuron. This mechanism empowers an efficient navigation strategy that outperforms the classical biased-random walk strategy. This general mechanism thus may be applicable to other sensory modalities for efficient gradient-based navigation.