Previous studies showed that natural walking reduces the susceptibility to VR sickness. However, many users still experience VR sickness when wearing VR headsets that allow free walking in room-scale spaces. This paper studies VR sickness and postural instability while the user walks in an immersive virtual environment using an electroencephalogram (EEG) headset and a full-body motion capture system. The experiment induced VR sickness by gradually increasing the translation gain beyond the user's detection threshold. A between-group comparison between participants with and without VR sickness symptoms found some significant differences in postural stability but found none on gait patterns during the walking. In the EEG analysis, the group with VR sickness showed a reduction of alpha power, a phenomenon previously linked to a higher workload and efforts to maintain postural control. In contrast, the group without VR sickness exhibited brain activities linked to fine cognitive-motor control. The EEG result provides new insights into the postural instability theory: participants with VR sickness could maintain their postural stability at the cost of a higher cognitive workload. Our result also indicates that the analysis of lower-frequency power could complement behavioural data for continuous VR sickness detection in both stationary and mobile VR setups.