Recently, due to the emergence of mobile electroencephalography (EEG) devices, assessment of mental workload in highly ecological settings has gained popularity. In such settings, however, motion and other common artifacts have been shown to severely hamper signal quality and to degrade mental workload assessment performance. Here, we show that classical EEG enhancement algorithms, conventionally developed to remove ocular and muscle artifacts, are not optimal in settings where participant movement (e.g., walking or running) is expected. As such, an adaptive filter is proposed that relies on an accelerometer-based referential signal. We show that when combined with classical algorithms, accurate mental workload assessment is achieved. To test the proposed algorithm, data from 48 participants was collected as they performed the Revised Multi-Attribute Task Battery-II (MATB-II) under a low and a high workload setting, either while walking/jogging on a treadmill, or using a stationary exercise bicycle. Accuracy as high as 95% could be achieved with a random forest based mental workload classifier with ambulant users. Moreover, an increase in gamma activity was found in the parietal cortex, suggesting a connection between sensorimotor integration, attention, and workload in ambulant users.