The current research explores six hypotheses derived from the well-known procedural justice-based model of legitimacy in two different religious groups in Israel, and adds to the model the effect of religiosity on the perceived legitimacy of rules and institutions of social control. Our results, based on data from a representative sample of 1,216 Israeli Jews and Arabs, provide general support for the hypotheses. We found that the social order is perceived as less legitimate by the Arab minority compared with the Jewish majority, and by highly religious members of the Jewish majority compared with those who are less religious.