Melilla, que no tenía a priori la importancia geoestratégica de Ceuta desde un punto de vista comercial al no situarse entre rutas transaharianas y la Península Ibérica, es decir, Europa, sí jugaba en cambio un papel relevante durante la época de dominio árabe como salida marítima de Fez, además de contar con unas salinas importantes, y su posición como mirador privilegiado ante al Mediterráneo musulmán.
En este contexto, en el siglo XIII se dan las primeras evidencias que vinculan Melilla con los reinos hispánicos, como así atestigua el Tratado de Monteagudo de las Vicarías, firmado por Juan II de Aragón y Sancho IV de Castilla en 1291. Ambos monarcas repartieron la zona de influencia de cada uno de sus reinos, fijando el límite entre ambas en el río Muluya, frontera natural de lo que hoy son Marruecos y Argelia, y cerca del cual se encuentran las Islas Chafarinas. Melilla, por tanto, quedaba así situada bajo el paraguas de influencia castellano.
La toma castellana definitiva de la fortaleza de Mililia tuvo lugar en 1497. Cuatro años antes, la ciudad vio desembarcar a Boabdil, rendida ya Granada, camino de Fez. Una expedición enviada por Don Juan de Guzmán, duque de Medina Sidonia, y encabezada por Pedro de Estopiñán, se hizo con la ciudad, que rápidamente comenzó a ser reforzada por las artes de Ramiro de Madrid, maestro fortificador que integraba la expedición y cuyos trabajos la convirtieron en inexpugnable en las embestidas siguientes que sufrió la ciudad por parte musulmana.
Además, y aunque sea poco conocido, Melilla condicionó la aventura indiana. El Duque de Medina Sidonia se hizo con la flota inicialmente destinada al tercer viaje de Cristóbal Colón para que Pedro de Estopiñán y sus tropas llegaran y tomaran la ciudad, con el consiguiente retraso en la nueva misión del genovés. Previamente, tres años antes, la división del mundo que habían firmado el 7 junio de 1494 los Reyes Católicos y Juan II de Portugal en el Tratado de Tordesillas modificó la línea imaginaria que partía en dos el globo para que Melilla, originalmente en zona portuguesa, pasara a estar bajo control castellano-aragonés, lo que a su vez permitió a Portugal otorgarse el dominio de lo que hoy es Brasil.
Las aspiraciones de los Reyes Católicos sobre el norte de África, una vez culminada la Reconquista en la Península Ibérica con la toma de Granada el 2 de enero de 1492, les habían llevado a fijarse en Melilla como plaza estratégica por su condición de frontera oriental del Reino de Fez, que a su vez tenía como frontera occidental la Ceuta portuguesa, y balcón privilegiado al Mediterráneo musulmán. Es decir, el Tratado de Tordesillas, además de dividir el mundo para los monarcas ibéricos, fijó dos cabezas de puente en el norte de África que resultaban estratégicas para la consolidación de la Reconquista católica de la Península Ibérica.
