Animal behavior is highly structured. Yet, structured behavioral patterns - or statistical ethograms - are not immediately apparent from the full spatiotemporal data that behavioral scientists usually collect. Here, we introduce a framework to characterize quantitatively rodent behavior during spatial (e.g., maze) navigation, in terms of movement building blocks or motor primitives. The hypothesis underlying this approach is that rodent behavior is characterized by a small number of motor primitives, which are combined over time to produce open-ended movements. We introduce a machine learning methodology - dictionary learning - which permits extracting motor primitives from rodent position and velocity data collected during spatial navigation and use them to both reconstruct past trajectories and predict novel ones. Three main results validate our approach. First, our method reconstructs rodent behavioral trajectories robustly from incomplete data, outperforming approaches based on standard dimensionality reduction methods, such as principal component analysis. Second, the motor primitives extracted during one experimental session generalize and afford the accurate reconstruction of rodent behavior across successive experimental sessions in the same or in modified mazes. Third, the number of motor primitives that our method associates to each maze correlates with independent measures of maze complexity, hence showing that the motor primitives formalism is sensitive to essential aspects of task structure. The framework introduced here can be used by behavioral scientists and neuroscientists as an aid for behavioral and neural data analysis. Indeed, the extracted motor primitives enable the quantitative characterization of the complexity and similarity between different mazes and behavioral patterns across multiple trials (i.e., habit formation). We exemplify some uses of the method to control for confounding effects (e.g., of maze complexity on behavior and reward collection), analyze habitual or stereotyped behavior, classify or predict behavioral choices as well as place and grid cell displacement in new mazes.