The aim of the present study was to investigate the effects of an audio-guided mindfulness (MF) single session on psychological and psychophysiological responses during an outdoor walking task. Twenty-four participants (12 females and 12 males; Mage = 23.6, SD = 3.9 years) were required to walk 200 m at a pace of their choosing. Two experimental conditions (mindfulness meditation and mindlessness [ML] meditation) and a control condition (CO) were administered. Electrical activity in the brain was measured by the use of a portable electroencephalography (EEG) system during walking. Fast Fourier Transform was used to decompose the EEG samples into theta (5–7 Hz), alpha (8–14 Hz), and beta (15–29 Hz) frequencies. Brain connectivity analysis between frontal and temporo-parietal electrode sites was conducted to explore functional interactions through the use of spectral coherence. Affective and perceptual responses were measured by the use of single-item scales and questionnaires. The present findings indicate that MF was sufficiently potent to reallocate attention toward task-related thoughts, downregulate perceived activation, and enhance affective responses to a greater degree than the other two conditions. Conversely, ML was sufficient to increase the use of dissociative thoughts, make participants less aware of their physical sensations and emotions, induce a more negative affective state, and upregulate perceived activation to a greater extent than MF and CO. The brain mechanisms that underlie the effects of MF on exercise appear to be associated with the enhanced inter-hemispheric connectivity of high-frequency waves between right frontal and left temporo-parietal areas of the cortex.