Patients with bilateral vestibular failure (BVF) suffer from gait unsteadiness, oscillopsia and impaired spatial orientation. Brain imaging studies applying caloric irrigation to patients with BVF have shown altered neural activity of cortical visual–vestibular interaction: decreased bilateral neural activity in the posterior insula and parietal operculum and decreased deactivations in the visual cortex. It is unknown how this affects functional connectivity in the resting brain and how changes in connectivity are related to vestibular impairment. We applied a novel data driven approach based on graph theory to investigate altered whole-brain resting-state functional connectivity in BVF patients (n= 22) compared to age- and gender-matched healthy controls (n= 25) using resting-state fMRI. Changes in functional connectivity were related to subjective (vestibular scores) and objective functional parameters of vestibular impairment, specifically, the adaptive changes during active (self-guided) and passive (investigator driven) head impulse test (HIT) which reflects the integrity of the vestibulo-ocular reflex (VOR). BVF patients showed lower bilateral connectivity in the posterior insula and parietal operculum but higher connectivity in the posterior cerebellum compared to controls. Seed-based analysis revealed stronger connectivity from the right posterior insula to the precuneus, anterior insula, anterior cingulate cortex and the middle frontal gyrus. Excitingly, functional connectivity in the supramarginal gyrus (SMG) of the inferior parietal lobe and posterior cerebellum correlated with the increase of VOR gain during active as compared to passive HIT, i.e., the larger the adaptive VOR changes the larger was the increase in regional functional connectivity. Using whole brain resting-state connectivity analysis in BVF patients we show that enduring bilateral deficient or missing vestibular input leads to changes in resting-state connectivity of the brain. These changes in the resting brain are robust and task-independent as they were found in the absence of sensory stimulation and without a region-related a priori hypothesis. Therefore they may indicate a fundamental disease-related change in the resting brain. They may account for the patients' persistent deficits in visuo-spatial attention, spatial orientation and unsteadiness. The relation of increasing connectivity in the inferior parietal lobe, specifically SMG, to improvement of VOR during active head movements reflects cortical plasticity in BVF and may play a clinical role in vestibular rehabilitation.