Having taken Ceuta in 818/1415, the Portuguese established a hold in Maghribī territory that would only be deepened in the ensuing decades, in such a way that, by 928/1521, one could, de facto, speak of two Portuguese protectorates in Western Maghribī territory, the first mainly set in Ceuta – Al- Qaṣr Al-Ṣaghīr – Tangier – Asīlah, and the second around the Doukkala region, set in the cities of Safī – Azammūr – el-Jadīda. All these encroachments in Marīnid (and, from 876/1471 on, Waṭṭāsid) sovereignty were made possible by the relative fragility of the Fez-based political center of the sultanate, whose control over coastal cities was flimsy, as much as by the intense internecine turmoil that beset these polities. This paper would, thus, aim at considering how both the Portuguese kingdom and Marīnid sultanate built their kingship legitimacies, this confrontation providing the necessary backdrop against which these parallel processes will be read. Special attention shall be given, on the Portuguese side, to how the royal intitulatio evolved to reflect the Portuguese conquests of tracts of Maghribī land, and on the notion of “service to God”, against the backdrop of a source-attested late medieval revival of the Crusade tradition and of the ideological tenet centered on the prolongation of the Iberian-based “Reconquista” process of earlier centuries, only this time in a Maghribī setting. On the Marīnid side, the notion of baraka, drawn from the repertoire of Sufi holy men, and its careful construction via meticulous stagecraft, public displays of generosity towards the subjects and public appearances of the sultan, will be considered so as to determine whether it reinforced or hindered the prestige of a politically declining dynasty. This paper shall thus confront Marīnid and Portuguese sources alike, mostly chronicles and chancery records, each one naturally predicated in its own politico-religious tradition of state-building, so as to i) highlight how building a legitimacy contributed to a better or worse control of the polity by each party, and ii) showcase the unique ideological mechanisms employed by both Muslims and Christians so as to claim dominion of the very same tract of land, thus baring each one’s singular worldview and mindset.