Objectives We sought to investigate the association between new-onset atrial fibrillation after coronary artery bypass graft (CABG) (post-operative atrial fibrillation POAF) and long-term mortality in patients with no history of atrial fibrillation. Background POAF predicts longer hospital stay and greater post-operative mortality. Methods A total of 16,169 consecutive patients with no history of AF who underwent isolated CABG at our institution between January 1, 1996, and December 31, 2007, were included in the study. All-cause mortality data were obtained from Social Security Administration death records. A multivariable Cox proportional hazards regression model was constructed to determine the independent impact of new-onset POAF on long-term survival after adjusting for several covariates. The covariates included age, sex, race, pre-operative risk factors (ejection fraction, New York Heart Association functional class, history of myocardial infarction, index myocardial infarction, stroke, chronic obstructive pulmonary disease, peripheral arterial disease, smoking, diabetes, renal failure, hypertension, dyslipidemia, creatinine level, dialysis, redo surgery, elective versus emergent CABG, any valvular disorder) and post-operative adverse events (stroke, myocardial infarction, acute respiratory distress syndrome, and renal failure), and discharge cardiac medications known to affect survival in patients with coronary disease. Results New-onset AF occurred in 2,985 (18.5%) patients undergoing CABG. POAF independently predicted long-term mortality (hazard ratio: 1.21; 95% confidence interval: 1.12 to 1.32) during a mean follow-up of 6 years (range 0 to 12.5 years). This association remained true after excluding from the analysis those patients who died in-hospital after surgery (hazard ratio: 1.21; 95% confidence interval: 1.11 to 1.32). Patients with POAF discharged on warfarin experienced reduced mortality during follow-up. Conclusions In this large cohort of patients, POAF predicted long-term mortality. Warfarin anticoagulation may improve survival in POAF.