Halal refers to what is permissible in traditional Islamic law. Food that meets halal requirements is marked by a halal label on the packaging and should be especially attractive to those Muslims who follow the set of dietary laws outlined in the Quran. This research examines the role of the halal label (explicit cue) and the country-of-origin (COO) (implicit cue) in predicting positive product perceptions among Muslim consumers. We hypothesized that when an explicit sign of “halalness” (i.e., halal label) relating to a particular product is accompanied by an implicit sign of anti-“halalness” (i.e., non-Islamic COO information), Muslim consumers who pay attention to the dietary laws of Islam would have negative perceptions of such a product. We tested our assumptions in an experiment conducted among Indonesian participants who declared themselves as Muslims (n = 444). We manipulated: (a) exposure to the halal label, and (b) the COO information. Religion-based purchase behavior was measured as a moderator variable. Positive product perceptions were measured as a dependent variable. The results showed that the halal label itself had limited influence on product perceptions. However, we found that positive product perceptions significantly decreased among people who were high in religion-based purchase behavior in response to exposure to non-Islamic COO information accompanied by a halal label. In conclusion, people who are high (vs. low) in religion-based purchase behavior do not seem to trust halal-labeled food produced in a country with other than an Islamic tradition.