Tras la conquista asidonense de Gibraltar de 1467, justificada mediante una donación del pretendiente "Alfonso XII", tanto este como del duque de Medina Sidonia fallecieron. El nuevo duque se apresuró a obtener del rey Enrique IV una merced similar que legitimara su situación. El monarca, buscando apoyos para recuperar el poder, se la concedió el 3 de junio de 1469. No contento, logró que el rey concediera a Gibraltar el Fuero de Antequera, consistente en la absoluta exención tributaria (20 de diciembre de 1470).
A la muerte de Enrique IV, en 1474, su hermana y heredera Isabel recabó apoyos para cimentar su posición en la Guerra de Sucesión que la enfrentaba con Juana la Beltraneja. Los Medina Sidonia fueron así gratificados con el Marquesado de Gibraltar (30 de septiembre de 1478). La ciudad permanecería bajo dominio asidonense 34 años, hasta que, ya bien asentados en su trono, los Reyes Católicos suprimieron el título el 22 de diciembre de 1501 y reincorporaron el territorio a los dominios realengos de la Corona de Castilla. El 2 de enero de 1502, Garcilaso de la Vega (padre), a la sazón comendador de Castilla, tomó posesión de la plaza y fue nombrado alcaide con 250 000 mrs de salario. En julio de ese año, la ciudad recibió sus armas. En 1504 murió Isabel la Católica, indicando en su testamento que Gibraltar debía permanecer en dominio de la Corona.
Despechado, el duque de Medina Sidonia, Juan Alonso Pérez de Guzmán, no cejaba en sus derechos, fundados en la donación de Enrique IV. Esperaba que el nuevo rey, Felipe el Hermoso, se la restituyese —y algunos historiadores de la casa de Medina Sidonia aseguran que así fue—, pero su súbita muerte acabó con tal esperanza. Aprovechando el caos provocado en Castilla por la muerte del rey, y creyéndose justificado para tomar el mismo posesión de la plaza, resolvió hacerlo por la fuerza.
Primero intentó el Duque tomar la plaza pretendiendo atraerse a la población local, que durante tantos años había permanecido para su dominio. Pero no solo no lo logró, sino que puso a los gibraltareños en alerta sobre sus pretensiones. Por tanto levantó un ejército que puso al mando de su hijo Enrique para asediar la ciudad, intentando presionarla para rendirse.
Diego López de Haro —alcaide interino por ausencia de Garcilaso de la Vega— y los gibraltareños se aprestaron a la defensa, escribiendo al capitán general del reino de Granada, el Conde de Tendilla, para que acudiera en su socorro.
El duque de Medina Sidonia fue conminado a levantar el cerco, pero se negó, anunciando que informaría al rey Fernando Diego Deza, el arzobispo de Sevilla, que le había prometido resolver en su favor sus pretensiones sobre Gibralrar gracias a su buena relación con la familia real. Finalmente, esta esperanza, unida a los preparativos militares en su contra, le llevaron a levantar el bloqueo sin que hubiera derramamiento de sangre, que ambas partes intentaron evitar.
En noviembre de 1506 la reina Juana y su consejo acordaron conceder a Gibraltar el título de "más leal ciudad" por su demostrada fidelidad en la denfensa contra los asidonenses. El duque de Medina Sidonia fue condenado a pagar los daños materiales causados por sus tropas a las propiedades de la población local, sin que se tuvieran en consideración sus reclamaciones sobre la propiedad de la plaza.
