When the Islamic empire emerged in the seventh century, it faced a twofold challenge: socializing its population to commit to a unified state that curtailed previous freedoms while subjecting itself to the requirement to adhere to the teachings of the religion through which it legitimized itself. In this presentation, I argue that this dual challenge crystallized in a debate about the rule of law that emerged as early as the first generation of Islam. The debate produced a distinctly constitutional political theory that came to structure classical Islamic law.