Severe asymptomatic stenosis of the internal carotid artery (ICA) leads to increased incidence of mild cognitive impairment (MCI) likely through silent embolic infarcts and/or chronic hypoperfusion, but the brain dysfunction is poorly understood and difficult to diagnose. Thirty cognitively intact subjects with asymptomatic, severe (≥ 70%), unilateral stenosis of the ICA were compared with 30 healthy controls, matched for age, sex, cardiovascular risk factors and education level, on a battery of neuropsychiatric tests, voxel-based morphometry of magnetic resonance imaging (MRI), diffusion tensor imaging and brain-wise, seed-based analysis of resting-state functional MRI. Multivariate regression models and multivariate pattern classification (support vector machines) were computed to assess the relationship between connectivity measures and neurocognitive performance. The patients had worse dizziness scores and poorer verbal memory, executive function and complex visuo-spatial performance than controls. Twelve out of the 30 patients (40%) were considered to have MCI. Nonetheless, the leukoaraiosis Sheltens scores, hippocampal and brain volumes were not different between groups. Their whole-brain mean fractional anisotropy (FA) was significantly reduced and regional functional connectivity (Fc) was significantly impaired in the dorsal attention network (DAN), frontoparietal network, sensorimotor network and default mode network. In particular, the Fc strength at the insula of the DAN and the mean FA were linearly related with attention performance and dizziness severity, respectively. The multivariate pattern classification gave over 90% predictive accuracy of individuals with MCI or severe dizziness. Cognitive decline in stroke-free individuals with severe carotid stenosis may arise from nonselective widespread disconnections of long-range, predominantly interhemispheric non-hippocampal pathways. Connectivity measures may serve as both predictors for cases at risk and therapeutic targets for mitigating vascular cognitive impairment.