Background Medications that impact insulin sensitivity or cause weight gain may increase heart failure risk. Our aim was to compare heart failure and cardiovascular death outcomes among patients initiating sulfonylureas for diabetes mellitus treatment versus metformin. Methods and Results National Veterans Health Administration databases were linked to Medicare, Medicaid, and National Death Index data. Veterans aged ≥18 years who initiated metformin or sulfonylureas between 2001 and 2011 and whose creatinine was <1.4 (females) or 1.5 mg/dL (males) were included. Each metformin patient was propensity score‐matched to a sulfonylurea initiator. The outcome was hospitalization for acute decompensated heart failure as the primary reason for admission or a cardiovascular death. There were 126 867 and 79 192 new users of metformin and sulfonylurea, respectively. Propensity score matching yielded 65 986 per group. Median age was 66 years, and 97% of patients were male; hemoglobin A _1c 6.9% (6.3, 7.7); body mass index 30.7 kg/m ² (27.4, 34.6); and 6% had heart failure history. There were 1236 events (1184 heart failure hospitalizations and 52 cardiovascular deaths) among sulfonylurea initiators and 1078 events (1043 heart failure hospitalizations and 35 cardiovascular deaths) among metformin initiators. There were 12.4 versus 8.9 events per 1000 person‐years of use (adjusted hazard ratio 1.32, 95% CI 1.21, 1.43). The rate difference was 4 heart failure hospitalizations or cardiovascular deaths per 1000 users of sulfonylureas versus metformin annually. Conclusions Predominantly male patients initiating treatment for diabetes mellitus with sulfonylurea had a higher risk of heart failure and cardiovascular death compared to similar patients initiating metformin.