Background The lipid hypothesis postulates that lower blood cholesterol is associated with reduced coronary heart disease (CHD) risk, which has been challenged by reports of a U‐shaped relation between cholesterol and death in recent studies. We sought to examine whether the U‐shaped relationship is true and to assess the impact of age on this association. Method and Results We conducted a prospective cohort study of 4 467 942 veterans aged >18 years, with baseline outpatient visits from 2002 to 2007 and follow‐up to December 30, 2018, in the Veterans Health Administration electronic health record system. We observed a J‐shaped relation between total cholesterol (TC) and CHD mortality after a comprehensive adjustment of confounding factors: flat for TC <180 mg/dL, and greater risk was present at higher cholesterol levels. Compared with veterans with TC between 180 and 199 mg/dL, the multiadjusted hazard ratios (HRs) for CHD death were 1.03 (95% CI, 1.02–1.04), 1.07 (95% CI, 1.06–1.09), 1.15 (95% CI, 1.13–1.18), 1.25 (95% CI, 1.22–1.28), and 1.45 (95% CI, 1.42–1.49) times greater among veterans with TC (mg/dL) of 200 to 219, 220 to 239, 140 to 259, 260 to 279 and ≥280, respectively. Similar J‐shaped TC‐CHD mortality patterns were observed among veterans with and without statin use at or before baseline. Conclusions The cholesterol paradox, for example, higher CHD death in patients with a low cholesterol level, was a reflection of reverse causality, especially among older participants. Our results support the lipid hypothesis that lower blood cholesterol is associated with reduced CHD. Furthermore, the hypothesis remained true when TC was low due to use of statins or other lipid‐lowering medication.