During spatial learning, subjects progressively adjust their navigation strategies as they acquire experience. The medial prefrontal cortex (mPFC) supports this operation, for which it may integrate information from distributed networks, such as the hippocampus (HPC) and the posterior parietal cortex (PPC). However, the mechanism underlying the prefrontal coordination with HPC and PPC during spatial learning is poorly understood. Here we show that during navigation trials, mice displayed two sequential behavioral stages: searching and exploration. Exclusively during searching, mice gradually increased their efficiency by transitioning from non-spatial to spatial strategies. When mice used spatial strategies specifically in searching stage, hippocampal and parietal oscillations synchronized gamma oscillations (60-100 Hz) and neuronal firing in the mPFC. This coincided with an increase in the incidence of gamma and task-stage-related changes in firing patterns in the mPFC. These findings relate the goal-directed organization of behavior during spatial learning to transient task-related prefrontal large-scale synchronization.