This dissertation examines three institutions that played an important role in the formation of the 7th-century Islamic polity. The first, emigration or hijra, begins as a policy of requiring or encouraging new members of the community to emigrate to the land of the believers. Two such hijras, to Abyssinia and to Yathrib/Medina, were performed by Muḥammad’s Meccan followers, who were thereafter known by the honorific Muhājirūn. The second, aʿrābiyya, begins with the application of the label aʿrāb to identify either the “Arabness” or “bedouinness” of various groups, including those who expressed their commitment to Islam but did not perform hijra. The third, which has deeper roots in pre-Islamic Arabia, is the mechanism of establishing subjecthood through the extension of a protection covenant, dhimma, whether to Muslims or peoples who maintained their own religion. The centrality of the three institutions is brought to the fore in the “Terms of Capitulation” tradition, which comprises instructions for the conduct of warfare given by the Prophet or, in other formulations, his first two successors (the caliphs Abū Bakr and ʿUmar). In Part I, I examine the textual and transmission data pertaining to the tradition and propose that a core portion of its legal substance is likely to originate with Muḥammad himself. In Part II, I interrogate the semantic evolution of the terminology (aʿrābiyya, hijra, and dhimma) on the basis of lexicographical, poetical, and epigraphic materials. I conclude that aʿrābiyya did not originally signify “bedouinness,” as it is commonly understood, but “Arabness,” that hijra was not an act of “abandonment” but related to the place of settlement, and that the Islamic practice of ascribing dhimma to God and His Messenger constituted a radical departure from the ancient tribal system. In Part III, I examine a range of historical, exegetical, and legal materials in which these concepts are articulated, seeking to understand the nature of Muḥammad’s relationship with the Arabian tribes who were the earliest targets of his diplomatic, military, and missionary endeavors. Sifting these sources for traces of early, pre-classical doctrine, I reconstruct the historical processes by which the standing of these groups was negotiated to achieve the unification of the polity. According to this reconstruction, early initiatives such as the artificial brotherhood enacted by Muḥammad between emigrants and residents, and the amendment of inheritance law such that bonds of kinship were replaced by bonds of Islam and hijra, are best understood as manifestations of the hijra-aʿrābiyya-dhimma framework. The objective of these policies, I propose, was to dilute tribal loyalties and establish a new social hierarchy that subordinated the tribes to God and Prophet. Oppositely, concepts that emerged in the course of the Islamic conquests, such as the notion of dhimma as a status occupied exclusively by non-Muslim subjects, and the perception of nomadism and nomadic groups as inferior and inherently deviant, were anachronistically projected onto the early Islamic milieu through juridical and exegetical exercise, and the subsequent refinement of traditions such as the Terms of Capitulation. The early, Arabian beginnings of the Islamic venture thus come to appear as distinctly separate from the period of Islamic empire, shaped by circumstances and concerns that evolved rapidly after Muḥammad’s lifetime.