This article analyses the influence of confessional divides in the construction of a Mediterranean frontier between the Iberian Peninsula and the Maghreb at the very beginning of the early modern period. Questioning the influence that religious difference had on the geopolitics of the early modern Mediterranean could seem superfluous since historians have traditionally depicted the Mediterranean world as a space of confrontation between two confessional empires, the Ottoman and the Habsburg. Nevertheless, by focusing on a selection of diplomatic negotiations from the Western Mediterranean it appears that several actors envisioned a scenario where religious and political frontiers were far from coincide. This article will analyse the diplomatic negotiations promoted by different Muslim communities from the Maghreb to voluntarily enter under the rule of the Catholic Monarchs in the framework of the Spanish imperial expansion at the beginning of the sixteenth century. In studying these negotiations from an actor-based approach my aim is not to deny the religious or the political divide existing between the Christian and the Islamic shores. I will argue, however, that this frontier was constructed through the interaction of a wide array of agents such as local elites, royal officers, military men, religious actors, and rulers, with changing agendas towards religious difference.