Although human cognition often occurs while moving, most studies of the dynamics of the human brain examine subjects while static and seated in a highly controlled laboratory. EEG signals have been considered to be too noisy to record brain dynamics during human locomotion. Here, we present a real-time ambulatory brain computer interface which allows us to detect gait phases and remove motion-related artifacts from EEG signals during walking in real-world environments. We first construct stride-based artifact templates employing a gyroscope to measure the angular velocity of the human body. Then, we apply an adaptive Kalman filter to estimate the mapping between the stride-based artifact template and EEG space, subtracting the motion-related noise from the raw EEG signal. This study demonstrates the robustness of our system to remove gait-related movement artifacts during human locomotion. Experiments in real-world environments show the potential practicality of reallife applications of low-cost wearable and wireless BCI systems for users actively working in and interacting with their environments.