Animals move in a wide variety of ways; the complex posture dynamics generating these behaviors span multiple spatiotemporal scales, and exhibit both regularity and variability. At large scales, behavior is structured, organized into stereotyped motifs such as walking or running, but the dynamics within each motif can be highly irregular. Despite the importance of behavior in fields ranging from neuroscience, ethology, control theory, robotics and artificial intelligence, to the physics of living systems; the complexity of movement presents unique challenges in quantification, analysis, and understanding. Advances in recording technology and recent progress in machine vision, now make it possible to gather high-resolution movement data, even in complex, naturalistic settings and for animals with intricate body plans. The next challenge is to characterize the dynamics in these recordings and develop a data-driven theory of animal locomotion. Here, we develop a behavioral state space in which the full instantaneous state is smoothly unfolded as a combination of short-time posture dynamics. Our technique, which is based on Takens delay embedding theorem, is tailored to multivariate observations and extends previous reconstructions through the use of maximal prediction. Applied to high-resolution video recordings of the roundworm C. elegans, we discover a low-dimensional state space dominated by three sets of cyclic trajectories corresponding to the worm’s basic stereotyped motifs: forward, backward, and turning locomotion. In contrast to this broad stereotypy, we find variability in the presence of locally-unstable dynamics, and this unpredictability shows signatures of deterministic chaos: a collection of unstable periodic orbits together with a positive maximal Lyapunov exponent. The full Lyapunov spectrum is symmetric with positive, chaotic exponents driving variability balanced by negative, dissipative exponents driving stereotypy. The symmetry is suggestive of damped, driven Hamiltonian dynamics underlying the worm’s movement control.