My dissertation offers the first social and legal history of the transition from Byzantine to Islamic Egypt (550–800), shifting our attention to actors in the Egyptian countryside—monks, bishops, and villagers—and the ways in which disputing, petitioning, and monastic disciplining influenced the texture of Islamic justice and institution-building. By integrating literary sources and material evidence from the underexplored archive of Arabic, Greek, and Coptic papyri, Recording Justice posits that Muslim state-building was never exclusively a matter of top-down imposition of political will and reforms by caliphs and governors. Instead, I argue that the social and legal expectations of the Egyptian populace—most of them Coptic Christians—were informed by centuries of Byzantine rule, and their expectations of scribal documentation, legal process, and authority actively shaped how, where, and when officials appointed by the Islamic state could dispense justice. Through the bottom-up use of papyri, Recording Justice resists the common periodization into pre-Islamic and Islamic, maintaining that a judicial crisis had been in the making in Egypt long before the Arab conquests in the 640s. The nature of this crisis was that the steady shift of power into the countryside enabled bishops, monks, and local administrators to accumulate substantial judicial and executive functions, resulting in access barriers to and the obsolescence of official courts as disputes were increasingly resolved through the more informal means of arbitration and mediation. Recording Justice reveals a new model of the Islamic state, which needed to negotiate with and garner acceptance from a rural populace that was predominantly non-Muslim and had specific ideas about how to be governed. The dissertation argues that shortly after the Arab Muslim conquests, state officials began issuing legal documents, specifically promissory notes (adhkār ḥaqq) and quittances (barāʾāt), recording the claims and entitlements of ordinary people in the Arabic language. By doing so, their legal claims became tied to the sovereignty of the fledgling Islamic state, guaranteed by a web of administrators, scribes, and witnesses, all of whom endowed these documents with their authoritative marks. By the late eighth century, the Islamic judiciary had ascended to the top tier in the administration of justice in Egypt, with political elites even deferring high-level political disputes to the judiciary. This development was undergirded by the judiciary’s growing reliance on a new type of legal document, the affidavit (iqrār), which operated under heightened standards of evidence and placed a premium on declarants’ legal accountability (taklīf). The affidavit not only became the hallmark of Islamic justice for centuries to come but also left a decisive mark on Coptic scribal culture. With that, Egypt transformed from an arbitration society into one in which official courts were once again accessible and where the presence of the Islamic judiciary as the top tier of justice functioned as an effective check on the powers of rural arbiters.