Several studies have identified Front-of-Pack Nutrition Labels (FoPLs) as a promising strategy to improve the nutritional quality of consumers’ food choices and encourage manufacturers to offer healthier products. This study aims to fill the evidence gap regarding the most effective FoPL among the Portuguese population. In total, 1059 Portuguese participants were recruited through a web panel provider and asked to declare their intended food choices and to rank three sets of products (pizza, cakes and breakfast cereals) according to their nutritional quality, first in the absence of any labelling, and then with a FoPL displayed on-pack (five FoPLs tested). Finally, participants were asked to answer nine statements related to perceptions of FoPLs. Results showed that participants improved their food choices, depending on the FoPL and the food category. All FoPLs led to a higher percentage of correct responses on the ranking task compared to the no label condition. The Nutri-Score was among the FoPLs producing the greatest improvement across all food categories compared to the reference intakes (OR = 6.45 [4.43–9.39], p-value < 0.0001) and facilitating the highest percentage to correctly rank products according to nutritional quality. This study suggests that, among the available options, Nutri-Score is the most efficient FoPL to inform Portuguese consumers of the nutritional quality of foods and help them identify healthier options in mock purchasing situations.