The differential impact of complete and incomplete bilateral vestibulopathy (BVP) on spatial orientation, visual exploration, and navigation-induced brain network activations is still under debate. In this study, 14 BVP patients (6 complete, 8 incomplete) and 14 age-matched healthy controls performed a navigation task requiring them to retrace familiar routes and recombine novel routes to find five items in real space. 18F-fluorodeoxyglucose-PET was used to determine navigation-induced brain activations. Participants wore a gaze-controlled, head-fixed camera that recorded their visual exploration behaviour. Patients performed worse, when recombining novel routes (p < 0.001), whereas retracing of familiar routes was normal (p = 0.82). These deficits correlated with the severity of BVP. Patients exhibited higher gait fluctuations, spent less time at crossroads, and used a possible shortcut less often (p < 0.05). The right hippocampus and entorhinal cortex were less active and the bilateral parahippocampal place area more active during navigation in patients. Complete BVP showed reduced activations in the pontine brainstem, anterior thalamus, posterior insular, and retrosplenial cortex compared to incomplete BVP. The navigation-induced brain activation pattern in BVP is compatible with deficits in creating a mental representation of a novel environment. Residual vestibular function allows recruitment of brain areas involved in head direction signalling to support navigation.