Recent archaeological, historical, and anthropological literature on the development of social and political complexity in Africa challenges older models of state formation that used to shape the understanding of medieval Sahelian empires, such as Songhay. As we now know, there were multiple paths to complexity that did not necessarily lead to state formation; and there was a heterarchical distribution of power in many African political formations. Nonetheless, the historiography of pre-colonial states in Sahelian West Africa, and of Islam’s role in these political formations, retains an attachment to a particular model of statehood derived from Arabic geographies and chronicles. Emphasis continues to be placed on military power and a largely ambivalent relation between Islam and indigenous forms of authority. In this article, a reinterpretation of the exercise and rhetoric of sovereignty in imperial Songhay is proposed that focuses on ways in which Islamic authority was claimed and contested byrulers. Songhay rulers claimed a religious authority that far outstripped their coercive power. Instead of an ambivalent relation between the Muslim religious estate and secular power, Islamic religious authority was the principal basis of Songhay rulers’ claims to extensive power.