Background Spontaneous heart rate fluctuations contain rich information related to health and illness in terms of physiological complexity, an accepted indicator of plasticity and adaptability. However, it is challenging to make inferences on complexity from shorter, more practical epochs of data. Distribution entropy (DistEn) is a recently introduced complexity measure that is designed specifically for shorter duration heartbeat recordings. We hypothesized that reduced DistEn predicted increased mortality in a large population cohort. Method and Results The prognostic value of DistEn was examined in 7631 middle-older-aged UK Biobank participants who had 2-minute resting ECGs conducted (mean age, 59.5 years; 60.4% women). During a median follow-up period of 7.8 years, 451 (5.9%) participants died. In Cox proportional hazards models with adjustment for demographics, lifestyle factors, physical activity, cardiovascular risks, and comorbidities, for each 1-SD decrease in DistEn, the risk increased by 36%, 56%, and 73% for all-cause, cardiovascular, and respiratory disease-related mortality, respectively. These effect sizes were equivalent to the risk of death from being >5 years older, having been a former smoker, or having diabetes mellitus. Lower DistEn was most predictive of death in those <55 years with a prior myocardial infarction, representing an additional 56% risk for mortality compared with older participants without prior myocardial infarction. These observations remained after controlling for traditional mortality predictors, resting heart rate, and heart rate variability. Conclusions Resting heartbeat complexity from short, resting ECGs was independently associated with mortality in middle- to older-aged adults. These risks appear most pronounced in middle-aged participants with prior MI, and may uniquely contribute to mortality risk screening.