The Health Star Rating (HSR) system is a voluntary front-of-pack labelling (FoPL) initiative endorsed by the Australian government in 2014. This study examines the impact of the HSR system on pre-packaged food reformulation measured by changes in energy density between products with and without HSR. The cost-effectiveness of the HSR system was modelled using a proportional multi-state life table Markov model for the 2010 Australian population. We evaluated scenarios in which the HSR system was implemented on a voluntary and mandatory basis (i.e., HSR uptake across 6.7% and 100% of applicable products, respectively). The main outcomes were health-adjusted life years (HALYs), net costs, and incremental cost-effectiveness ratios (ICERs). These were calculated with accompanying 95% uncertainty intervals (95% UI). The model predicted that HSR-attributable reformulation leads to small changes in mean population energy intake (voluntary: −0.98 kJ/day; mandatory: −11.81 kJ/day). These are likely to result in changes in mean body weight (voluntary: −0.01 kg [95% UI: −0.012 to −0.006]; mandatory: −0.11 kg [95% UI: −0.14 to −0.07]), and HALYs gained (voluntary: 4207 HALYs gained [95% UI: 2438 to 6081]; mandatory: 49,949 HALYs gained [95% UI: 29,291 to 72,153]). The HSR system could be considered cost-effective relative to a willingness-to-pay threshold of A$50,000 per HALY (incremental cost effectiveness ratio for voluntary: A$1728 per HALY [95% UI: dominant to 10,445] and mandatory: A$4752 per HALY [95% UI: dominant to 16,236]).