What are the fundamental principles by which brains perform computations to serve behavioral goals? Historical ethology studies suggest that behavioral programs are organized in a hierarchical manner, where overarching drives consist of finer-scale motor programs and actions. How such an organization could be achieved at the neuronal level remains largely elusive. We address this problem by studying the tractable tiny soil worm C. elegans. To date, it is the only nervous system for which a complete neuronal network graph has been mapped.Despite the small size of its brain, the worm performs complex behaviors. For example, the worm orchestrates a variety of motor actions for exploration during food search. Using quantitative behavioral analysis, we show that this organization can indeed be described in a hierarchical manner: some motor programs executed on a longer timescale (seconds to minutes) can be subdivided into shorter postural syllables that enable different behavioral strategies, like local exploration or long-distance travelling.We set out to investigate how this organization is represented neuronally and therefore developed fast fluorescence microscopy techniques, enabling us to record the activity of nearly all of the animals nerve cells, simultaneously and in real time. We discovered that the worms brain is not merely a reflexive input-output device; rather, it exhibits a wealth of intrinsic activities involving a large fraction of all of its interneurons and motor neurons. However, these neuronal network dynamics are highly coordinated to form low dimensional network attractors that oscillate between various states. In addition, our datasets revealed smaller units of motor-neuron circuits that exhibit central-pattern-generator (CPG) like activity, and whose higher frequency oscillations are phase-nested within the larger-scale brain wide oscillations. A functional characterization of these dynamics revealed that the brain wide oscillations represent the switching between the major overarching motor programs, and that the nested CPG oscillations are neural correlates of the shorter postural syllables.Our results suggest that the worm brain operates like a dynamical system in which coupling and phase-nesting of intrinsically oscillating neuronal ensembles is a means of information processing to organize its actions hierarchically across timescales. Interestingly, similar neuronal principles can be observed in the study of cognition in higher animals. The tiny soil worm thus presents a unique opportunity to better understand these general neuronal phenomena at the level of mechanistic insights.