Background: The Health Star Rating (HSR) is the government-endorsed front-of-pack labeling system in Australia and New Zealand. Objectives: We aimed to examine prospective associations of a dietary index (DI) based on the HSR, as an indicator of overall diet quality, with all-cause and cardiovascular disease (CVD) mortality. Methods: We utilized data from the national population-based Australian Diabetes, Obesity and Lifestyle Study. The HSR-DI at baseline (1999-2000) was constructed by 1) calculation of the HSR points for individual foods in the baseline FFQ, and 2) calculation of the HSR-DI for each participant based on pooled HSR points across foods, weighted by the proportion of energy contributed by each food. Vital status was ascertained by linkage to the Australian National Death Index. Associations of HSR-DI with mortality risk were assessed by Cox proportional hazards regression. Results: Among 10,025 eligible participants [baseline age: 51.6 ± 14.3 y (mean ± standard deviation)] at entry, higher HSR-DI (healthier) was associated with higher consumption of healthy foods such as fruits, vegetables, and nuts, and lower consumption of discretionary foods such as processed meats and confectionery (P-trend < 0.001 for each). During a median follow-up of 16.9 y, 1682 deaths occurred with 507 CVD deaths. In multivariable models adjusted for demographic characteristics, lifestyle factors, and medical conditions, higher HSR-DI was associated with lower risk of all-cause mortality, with a hazard ratio (95% confidence interval) of 0.80 (0.69, 0.94; P-trend < 0.001) comparing the fifth with the first HSR-DI quintile. A corresponding inverse association was observed for CVD mortality (0.71; 0.54, 0.94; P-trend = 0.008). Conclusions: Better diet quality as defined by the HSR-DI was associated with lower risk of all-cause and CVD mortality among Australian adults. Our findings support the use of the HSR nutrient profiling algorithm as a valid tool for guiding consumer food choices.