Alternative patterns of neural activity drive different rhythmic locomotory patterns in both invertebrates and mammals. The neuro-molecular mechanisms responsible for the expression of rhythmic behavioral patterns are poorly understood. Here we show that Caenorhabditis elegans switches between distinct forms of locomotion, or crawling versus swimming, when transitioning between solid and liquid environments. These forms of locomotion are distinguished by distinct kinematics and different underlying patterns of neuromuscular activity, as determined by in vivo calcium imaging. The expression of swimming versus crawling rhythms is regulated by sensory input. In a screen for mutants that are defective in transitioning between crawl and swim behavior, we identified unc-79 and unc-80, two mutants known to be defective in NCA ion channel stabilization. Genetic and behavioral analyses suggest that the NCA channels enable the transition to rapid rhythmic behaviors in C. elegans. unc-79, unc-80, and the NCA channels represent a conserved set of genes critical for behavioral pattern generation.