Gender differences in electroencephalographic activity (EEG) changes during navigation task performance after training were assessed in young adults. Female and male subjects were matched on initial navigation performance. EEG recordings were obtained while subjects navigated in an immersive virtual environment without visual cues, before and after a navigational skills training (9 sessions). In spite of task performance was similar in both groups, females showed higher theta band coherent activity between frontal and parietal and frontal and central regions than males before training. Correlation in theta band between fronto-central, fronto-parietal, and centro-parietal regions was enhanced in the left hemisphere for females but in the right hemisphere for males after training. Females also demonstrated a decreased in correlation in theta band over the right hemisphere between centro-parietal regions, whereas males demonstrated a similar effect over the left hemisphere. Navigation training seems to promote fronto-central-parietal synchronization in both genders but in different hemisphere. These results are interpreted as reflecting verbal-analytical working memory functions in females and global-spatial working memory mode in males.