In Australia, manufacturers can use two government-endorsed approaches to advertise product healthiness: the Health Star Rating (HSR) front-of-pack nutrition labelling system, and health claims. Related, but different, algorithms determine the star rating of a product (the HSR algorithm) and eligibility to display claims (the Nutrient Profiling Scoring Criterion (NPSC) algorithm). The objective of this study was to examine the agreement between the HSR and NPSC algorithms. Food composition information for 41,297 packaged products was extracted from The George Institute’s FoodSwitch database. HSR and the NPSC scores were calculated, and the proportion of products in each HSR category that were eligible to display a health claim under the NPSC was examined. The highest agreement between the HSR scoring algorithm and the NPSC threshold to determine eligibility to display a health claim was at the HSR cut-off of 3.5 stars (k = 0.83). Overall, 97.3% (n = 40,167) of products with star ratings of 3.5 or higher were also eligible to display a health claim, and 94.3% (n = 38,939) of products with star ratings less than 3.5 were ineligible to display a health claim. The food group with greatest divergence was “edible oils”, with 45% products (n = 342) with HSR >3.5, but 64% (n = 495) eligible to display a claim. Categories with large absolute numbers of products with HSR <3.5, but eligible to display a claim, were “yoghurts and yoghurt drinks” (335 products, 25.4%) and “soft drinks” (299 products, 29.7%). Categories with a large number of products with HSR ≥3.5, but ineligible to display a claim, were “milk” (260 products, 21.2%) and “nuts and seeds” (173 products, 19.7%). We conclude that there is good agreement between the HSR and the NPSC systems overall, but divergence in some food groups is likely to result in confusion for consumers, particularly where foods with low HSRs are eligible to display a health claim. The alignment of the NPSC and HSR scoring algorithms should be improved.