Animals navigating turbulent odor plumes exhibit a rich variety of behaviors, and employ efficient strategies to locate odor sources. A growing body of literature has started to probe this complex task of localizing airborne odor sources in walking mammals to further our understanding of neural encoding and decoding of naturalistic sensory stimuli. However, correlating the intermittent olfactory information with behavior has remained a long-standing challenge due to the stochastic nature of the odor stimulus. We recently reported a method to record real-time olfactory information available to freely moving mice during odor-guided navigation, hence overcoming that challenge. Here we combine our odor-recording method with head-motion tracking to establish correlations between plume encounters and head movements. We show that mice exhibit robust head-pitch motions in the 5-14Hz range during an odor-guided navigation task, and that these head motions are modulated by plume encounters. Furthermore, mice orient towards the odor source upon plume contact. Head motions may thus be an important part of the sensorimotor behavioral repertoire during naturalistic odor-source localization.