La permanence de la présence espagnole sur la côte marocaine a été, très tôt, sujet à débat en Espagne eu égard aux énormes frais que cela représentait pour les finances de l'État espagnol.
Nous ne retiendrons de toute cette longue période qui s'étale entre les conquêtes du XVe siècle et la première moitié du XIXe que deux dates qui illustrent le mieux les doutes espagnols face à la situation des deux villes et des peñones adjacents. Ainsi, en 1811, alors que l'Espagne vit une période difficile face aux troupes napoléoniennes –la Guerra de Independencia- les Cortes de Cadix envisagent-elles la cession des Presidios menores[1] en échange d'argent et de vivres pour poursuivre la lutte contre l'envahisseur français. Finalement, malgré un vote des Cortes favorable à la cession, celle-ci n'aura pas lieu.
En 1821 également, au cours de la période appelée Trienio liberal, la cession des plazas menores est décidée par les Cortes, mais ce sont cette fois des difficultés intérieures marocaines qui empêcheront le projet de se concrétiser.
Outre ces tentatives d'abandon, quelle place a été accordée aux deux villes dans les différentes Contitutions espagnoles ? La première Constitution, celle de 1812, aborde dans son article "Du territoire des Espagnes" la place de Ceuta et Melilla dans le territoire national. Au terme de discussions acharnées, elles ne seront pas citées expressément et seulement regroupées dans l'expression y demás posesiones en África : ainsi ne sont-elles pas considérées comme faisant partie du territoire espagnol ni des territoires d'outre-mer.
Après une certaine période de confusion sur leur statut, confusion entretenue par l'instauration du Protectorat en 1912 qui distingue les "Territoires de Souveraineté" des "Territoires protégés" dans lesquels les deux villes sont pourtant incluses, il faudra attendre la Constitution de 1978 pour que Ceuta et Melilla soient enfin expressément nommées dans le processus autonomique. Il s'agit de la fameuse Disposición Transitoria Quinta qui stipule que :
Las ciudades de Ceuta y Melilla podrán constituirse en Comunidades Autónomas si así lo deciden sus respectivos Ayuntamientos, mediante acuerdo adoptado por la mayoría de sus miembros y así lo autorizan las Cortes Generales mediante una ley orgánica, en los términos previstos en el artículo 144.
C'est chose faite depuis 1995 et, même si les deux villes espagnoles n'ont ni le titre de Communauté Autonome ni la capacité législative qui va avec, leur nouveau statut de Ciudad Autónoma leur accorde, pour la première fois de leur histoire, une place à part entière dans la nouvelle organisation administrative de l'Espagne
[1] À cette époque, une distinction est faite entre Ceuta et les presidios menores –Melilla, le peñón de Velez de la Gomera et le peñón de Alhucemas-. Plus tard, quand la plaza de Melilla aura accru sa population au début du XXe siècle, on fera la distinction entre presidios mayores –Ceuta et Melilla- et presidios menores –les peñones et les îles Chafarinas récemment conquises.