Arabic legal documents from early Islamic Egypt are attested in Arabic papyrus collections. These exhibit a formulaic structure that is clearly distinct from those of the Byzantine Greek tradition of legal documents, which continued to be written in the first Islamic century. The Islamic Arabic documents reflect a legal formulaic tradition that had its origins in the Ḥijāz of Arabia. This article examines the background of this Ḥijāzī tradition, with particular focus on the opening formula and the witness clauses. Parallel features are identified in Ancient South Arabian legal texts and in texts of legal nature from Northern Arabia.