This article is intended as a contribution to the debate on the nature of the early Islamic state (especially 1–70 AH/622–690 AD), as regards both its government and its ideology. It presents and discusses new documentary evidence that sheds light on these subjects and tries to advance a little further the discussion of two questions that have been particularly hotly debated in recent years. These are: whether the Muslims merely continued the administrative practices of the Byzantines and Persians or introduced innovations, and why recognizably Islamic messages do not appear in the material record before the reign of the caliph ‘Abd al-Malik (65–85 AH/685–705 AD). Finally, this article attempts to draw attention to the relative under-use of documents, whether papyri, coins, rock inscriptions or the like, and to illustrate the different ways in which they might be deployed to enhance our knowledge of this very important topic.