Dès la conquête de Ceuta (1415) par les Portugais et de Melilla (1497) par les Espagnols, les musulmans sont chassés des deux villes et leur réinstallation rendue impossible puisque, d'emblée, des relations conflictuelles s'instaurent entre les chrétiens retranchés à l'intérieur des villes et les musulmans qui cherchent à les en chasser.
Pendant la longue période d'occupation ibérique, la population des deux villes se caractérise principalement par sa composante militaire à laquelle s'ajoutent quelques civils (professions libérales, personnels de l'administration, prêtres et même prostituées). Enfin un dernier groupe de population complète les deux premiers : celui des prisonniers quand Ceuta et Melilla sont utilisées comme lieux de déportation. C'est cette fonction de bagne qui laissera le nom de presidios pour désigner les possessions espagnoles sur les côtes marocaines. Ainsi, peut-on affirmer qu'avant le début du XXe siècle, Ceuta et Melilla ne sont pas des "villes" à proprement parler car elles n'ont pas de population stable mais plutôt une population qui se renouvelle et fluctue au gré des événements militaires. À titre d'exemple, citons les chiffres de la population de Ceuta en 1847 : sur un total de 6 896 habitants, 2 555 sont des militaires, 2 131 sont des prisonniers et seulement 2 210 sont des civils. À Melilla, la même année, la population civile s'élève à 198 personnes pour 1 500 militaires et 400 prisonniers. S'il est certain que la place des militaires dans les deux villes a toujours été prépondérante car ils y détenaient tous les postes-clés, la tendance militariste qui apparaît durant l'escalade militaire du début du XXe siècle, ne fait qu'accentuer le rôle de ces derniers.
Cependant, après 1863, la structure de la population va considérablement être modifiée : Ceuta et Melilla sont transformées en ports francs dans le but de leur donner un nouvel essor fondé essentiellement sur le commerce. Les deux villes s'ouvrent alors à la population juive du Maroc même si l'installation de musulmans est encore interdite en cette fin du XIXe siècle. Quant à la population civile d'origine péninsulaire, elle connaît une progression prodigieuse dans les années qui suivent : au cours de la décennie 1900-1910 la population de Melilla augmente de 445 % tandis que celle de Ceuta connaît un accroissement de 110 %. Ce développement démographique est lié au développement commercial et industriel des deux villes espagnoles qui deviennent alors les "portes d'entrée" du tout nouveau Protectorat instauré en 1912. C'est aussi à cette époque que s'installent les premiers membres de la communauté hindoue venus de Gibraltar pour se consacrer au commerce et qui forment encore aujourd'hui, une des composantes originales de la population de Ceuta et Melilla.
Mais sans aucun doute, c'est l'accroissement de la population musulmane en provenance du Maroc qui reste la principale originalité de la population actuelle de Ceuta et de Melilla. À Melilla en particulier, la population musulmane passe de 118 en 1897 à 6 277 en 1950 ; en 1995, elle est estimée à 26 000 personnes et représente environ 30 % de la population totale. Les décennies 1940-1950, pendant le Protectorat, sont les années de plus forte installation musulmane. Cette population se caractérise aujourd'hui par sa jeunesse, son fort taux d'analphabétisme et son important taux de chômage.
Nul doute que son intégration sociale représente aujourd'hui le principal défi lancé à la démocratie espagnole dans les deux villes.