A 66-year-old man presented with mild amnesia, progressive fatigue, ataxia, visual hallucinations, and debility. His past medical history included right-sided carotid endarterectomy performed elsewhere 6 years previously. Cranial magnetic resonance imaging showed left parieto-occipital arteriovenous malformation-like tortous vessels, venous congestion, and ischemic areas. Cerebral angiography showed right-sided compound external carotid artery-internal jugular vein (IJV) fistula, and distal occlusion of the right IJV. Transvenous embolization via contralateral IJV was performed, and the fistula, together with fistulous portion of the distal IJV, was sealed using coils. Two years later, patient is well with normal neurologic examination findings. The presence of an arteriovenous communication after vascular surgery is a serious complication with potential long-term effects and therefore should be diagnosed and treated as promptly as possible.