Background Coronary artery bypass grafting (CABG) is often used to treat patients with significant coronary heart disease (CHD). To date, multiple longitudinal and cross-sectional studies have examined the association between depression and CABG outcomes. Although this relationship is well established, the mechanism underlying this relationship remains unclear. The purpose of this study was twofold. First, we compared three markers of autonomic nervous system (ANS) function in four groups of patients: 1) Patients with coronary heart disease and depression (CHD/Dep), 2) Patients without CHD but with depression (NonCHD/Dep), 3) Patients with CHD but without depression (CHD/NonDep), and 4) Patients without CHD and depression (NonCHD/NonDep). Second, we investigated the impact of depression and autonomic nervous system activity on CABG outcomes. Methods Patients were screened to determine whether they met some of the study's inclusion or exclusion criteria. ANS function (i.e., heart rate, heart rate variability, and plasma norepinephrine levels) were measured. Chi-square and one-way analysis of variance were performed to evaluate group differences across demographic, medical variables, and indicators of ANS function. Logistic regression and multiple regression analyses were used to assess impact of depression and autonomic nervous system activity on CABG outcomes. Results The results of the study provide some support to suggest that depressed patients with CHD have greater ANS dysregulation compared to those with only CHD or depression. Furthermore, independent predictors of in-hospital length of stay and non-routine discharge included having a diagnosis of depression and CHD, elevated heart rate, and low heart rate variability. Conclusions The current study presents evidence to support the hypothesis that ANS dysregulation might be one of the underlying mechanisms that links depression to cardiovascular CABG surgery outcomes. Thus, future studies should focus on developing and testing interventions that targets modifying ANS dysregulation, which may lead to improved patient outcomes.