Dietary risk factors, including excess added sugar intake, are leading contributors to Australia’s burden of disease. An objective of the Australian Health Star Rating (HSR) system is to encourage the reformulation of packaged foods. Manufacturers may improve a product’s HSR by replacing added sugar with non-nutritive sweeteners (NNS). Concerns have been raised regarding the potential substitution effects of ultra-processed foods containing NNS for whole foods, and the long-term impact this may have on population health. The aim of this study was to determine whether the implementation of the HSR system has impacted the use of added sugars and NNS in the food supply. Four product categories were used: products with no added sweetener, products containing added sugar only, products containing NNS only, and products containing a combination of added sugar and NNS. Of 6477 newly released products analyzed displaying a HSR in Australia between 2014–2020, 63% contained added sugars. The proportion of new products sweetened with added sugars increased over time, while NNS use did not, despite a higher average and median HSR for products sweetened with NNS. These findings suggest that at the current time, the HSR system may not discourage the use of added sugars in new products or incentivize the reformulation of added sugar with NNS. As the health risks of NNS are questioned, increased reformulation of products with NNS to reduce the presence of added sugar in the food supply may not address broader health concerns. Instead, supporting the promotion of whole foods and drinks should be prioritized, as well as policy actions that reduce the proliferation and availability of UPFs.