Objective Occurrence of a stroke within 30 days following coronary artery bypass grafting (CABG) is an uncommon, but often devastating, complication. This study aimed to identify factors associated with long-term survival (beyond 30 days) in patients with stroke after CABG. Methods De-identified patients’ records from the Veterans Affairs Surgical Quality Improvement Program database were used to identify risk factors and perioperative complications associated with survival for up to 20 years in patients with post-CABG stroke. The multivariable Cox proportional hazards model was used for analyzing survival. Results The median survival time for patients with stroke (n = 1422) was 6.7 years. The mortality rate for these patients was highest in the first year post-CABG and was significantly elevated compared with non-stroke patients. Survival rates at 1, 5, and 10 years for stroke versus non-stroke patients were 79% vs. 96%, 58% vs. 83%, and 36% vs. 63%, respectively. High preoperative serum creatinine levels, postoperative occurrence of renal failure, prolonged ventilation, coma, and reoperation for bleeding were important predictors of 1-year mortality of patients with post-CABG stroke. Conclusions Veterans with post-CABG stroke have a considerably higher risk for mortality during the first year compared with patients without stroke.