This study offers a sociolegal interpretation of the ancient extant document generally referred to in modern scholarship as the “Constitution of Medina,” showing it to be a three-part composite document written between 622 and 627. Each part has considerable formal coherence as a legal deed. The first part was the deed of foundation of Muhammad's umma, not yet a community of individual believers but a confederation of clans and their clients unified in the struggle in the path of God. The execution of capital punishment for murder was transferred from the clans to the community. The second part guaranteed religious freedom to Jewish confederates, thus laying the foundation of the later Muslim system of religious pluralism; it created the first Muslim sanctuary (ḥarām) and introduced elements of individual responsibility. The third part, here considered a supplement to the second, concerned the defense of the city of Medina against the Quraysh and added one new Jewish clan to the confederation. Taken together, the three parts of the Constitution of Medina transformed the pagan cult of vengeance into holy warfare.