This dissertation focuses on how the Marrakech-based Almohads and their independent Muslim rivals in eastern al-Andalus contested spiritual and temporal power. The rulers of Sharq al-Andalus opposed Almohad claims to a divinely granted authority rooted in a new messianic interpretation of the caliphate. Instead, they articulated a vision of legitimacy linked to earlier Sunni forms, and connected their rule more closely to the Abbasid caliphate in Baghdad than any previous Andalusī dynasty had done. One minted coins that included the name of the Abbasid caliph, and another received official permission from the Abbasids to rule as governor of al-Andalus. This dissertation examines the written sources, coins and architecture produced in the courts of Andalusī and Almohad rulers to explore how they legitimated their authority. It argues that the conflict among these Muslim rivals in many ways superseded their battles against Christians. The Almohads saw anyone—Muslim, Christian or Jewish—who did not submit to their rule and their conception of Islam as infidels, and said that jihad against non-Almohad Muslims was more important than jihad against Christians. Nevertheless, later Arabic sources attempted to cast the conflict between the independent rulers of al-Andalus and the Almohads as part of a broader Christian-Muslim clash. The alliances Andalusī rulers made with Christian kings, and, in some cases, their Christian roots, made their religious allegiance to Islam suspect. This attitude has continued in modern scholarship as well. This dissertation instead argues that the independent rulers of al-Andalus and their Almohad counterparts were engaged in a broader debate, common to the wider Islamic world, about what constituted righteous Islamic authority. As the population of the territories ruled by Muslims became majority Muslim, new groups began to gain power, eroding the primacy of the Arab caliphate. Like their Persian and Turkic contemporaries to the east, the Berber and Andalusī rulers of the Islamic west struggled to negotiate between the caliphal ideal of Islamic unity and the increasingly decentralized political world they encountered. Analyzing the conflicts among these rivals illuminates the questions that animated the Islamic world as new spiritual and political forms were emerging.