Video gaming is a highly pervasive activity, providing a multitude of complex cognitive and motor demands. Gaming can be seen as an intense training of several skills. Associated cerebral structural plasticity induced has not been investigated so far. Comparing a control with a video gaming training group that was trained for 2 months for at least 30 min per day with a platformer game, we found significant gray matter (GM) increase in right hippocampal formation (HC), right dorsolateral prefrontal cortex (DLPFC) and bilateral cerebellum in the training group. The HC increase correlated with changes from egocentric to allocentric navigation strategy. GM increases in HC and DLPFC correlated with participants’ desire for video gaming, evidence suggesting a predictive role of desire in volume change. Video game training augments GM in brain areas crucial for spatial navigation, strategic planning, working memory and motor performance going along with evidence for behavioral changes of navigation strategy. The presented video game training could therefore be used to counteract known risk factors for mental disease such as smaller hippocampus and prefrontal cortex volume in, for example, post-traumatic stress disorder, schizophrenia and neurodegenerative disease.