Chemotaxis during sinusoidal locomotion in nematodes captures in simplified form the general problem of how dynamical interactions between the nervous system, body, and environment are exploited in the generation of adaptive behavior. We used an evolutionary algorithm to generate neural networks that exhibit klinotaxis, a common form of chemotaxis in which the direction of locomotion in a chemical gradient closely follows the line of steepest ascent. Sensory inputs and motor outputs of the model networks were constrained to match the inputs and outputs of the Caenorhabditis elegans klinotaxis network. We found that a minimalistic neural network, comprised of an ON-OFF pair of chemosensory neurons and a pair of neck muscle motor neurons, is sufficient to generate realistic klinotaxis behavior. Importantly, emergent properties of model networks reproduced two key experimental observations that they were not designed to fit, suggesting that the model may be operating according to principles similar to those of the biological network. A dynamical systems analysis of 77 evolved networks revealed a novel neural mechanism for spatial orientation behavior. This mechanism provides a testable hypothesis that is likely to accelerate the discovery and analysis of the biological circuitry for chemotaxis in C. elegans.