En los años que siguieron a la destrucción y abandono de la ciudad, los términos de las Algeciras -como se denominan en la documentación de los siglos XV y XVI- quedaron convertidos en baldíos, conformando una amplia zona fronteriza o tierra de nadie situada entre los territorios castellanos de Tarifa, Medina Sidonia y Alcalá de los Gazules y los enclaves granadinos de Gibraltar y Castellar.

Esta situación debió perdurar durante varias décadas, en tanto que existió un estado de inseguridad en la zona a causa de la ruptura de las treguas entre castellanos y nazaríes. Sin embargo, el rey Juan I (1379-1390), preocupado por la guerra que lo enfrentaba a Portugal e Inglaterra, creyó conveniente atraerse la amistad de Granada y concertó con Muhammad V un tratado de paz que iba a prolongarse a lo largo de su reinado y también durante el reinado de su sucesor, Enrique III. Las nuevas relaciones de amistad entre Castilla y Granada -no exentas de esporádicas algaradas organizadas desde uno u otro lado de la frontera- iban a permitir que los concejos castellanos cercanos a los términos de la destruida Algeciras (Tarifa, Jerez, Medina Sidonia y Alcalá) comenzaran a hacer uso de los mismos, dado su total abandono, aprovechando sus dehesas para pasto del ganado, sus montes para la saca de leña y sus aguas litorales para pescar (Carta del rey Enrique IV autorizando a los concejos de Jerez y Tarifa a aprovechar los términos que habían pertenecido a las Algeciras (Archivo General de Simancas, 27 de junio de 1481). Sabemos que en el siglo XV, las autoridades de Tarifa alegaban, para demostrar la legalidad de las tierras ocupadas en el antiguo territorio algecireño, que su ciudad había recibido en el año 1383 una parte de los términos de Algeciras para su uso y aprovechamiento (Archivo Ducal de Medinaceli, Sección Medinaceli, Leg. 228).  

Retrato del rey Enrique IV

En 1439 pudo haberse reconstruido la ciudad y repoblado de nuevo su territorio, como se ha referido en un artículo anterior, al menos, estuvo en la mesa de negociaciones mantenidas entre los reyes de Castilla y Granada la posibilidad de que se llevara a cabo tal proyecto. En ese año se inició una serie de encuentros entre embajadores de los reyes castellano y granadino con el objeto de redactar las estipulaciones que habrían de contener el nuevo tratado de paz a concertar entre ambos reinos. Una de las cláusulas que Juan II exigía para llevar a feliz término las conversaciones, era que el rey de Granada debía comprometerse a reconstruir la ciudad de Algeciras a su costa, "por cuanto fueron destruidas (las Algeciras) por los moros estando en tregua y seguridad" o, en caso contrario, tendría que pagar el granadino la suma que tasadores imparciales calcularan sobre los daños causados a la ciudad, según documentación conservada en el Archivo de los Duques del Infantado, (Cajón 3, Leg. 1). Muhammad IX no aceptó esta gravosa cláusula y las Algeciras continuaron convertidas en un montón de ruinas. Las paces se firmaron finalmente en abril de 1439. 

En el año 1462, los castellanos consiguieron tomar la ciudad de Gibraltar a los nazaríes. Como el término de esa enriscada ciudad era poco extenso y muy abrupto, pues sólo ocupaba una estrecha franja de tierra situada entre el río Guadarranque, Sierra Carbonera y el propio Peñón, el rey Enrique IV decidió donar los términos de las antiguas Algeciras al recién instaurado concejo gibraltareño para que los vecinos que lo vinieran a poblar "puedan pacer e pascan con sus ganados e puedan labrar e sembrar e plantar viñas e huertas".  

Tarifa y Jerez, que venían disfrutando de los abandonados términos de Algeciras desde finales del siglo XIV, alegaron tener derechos adquiridos sobre ciertos "echos e campos" de las Algeciras, de los que ahora se veían desposeídos por la provisión real, y recurrieron ante las autoridades judiciales para hacer valer lo que ellos consideraban sus derechos de posesión. Por tal motivo se mantuvo un largo contencioso entre el concejo de Tarifa y el Duque de Medina Sidonia -luego con el concejo de Gibraltar-, hasta que se resolvió el pleito por sentencia definitiva favorable a Gibraltar dada en el año I514 por la Real Chancillería de Granada.  

Provisión real de los Reyes Católicos dirigida al Adelantado Mayor de la Frontera y al concejo de Tarifa instando a esta villa a que restituya los “echos e campos”, que habían pertenecido a Algeciras, a la ciudad de Gibraltar. 4 de enero de 1485

De los diversos documentos conservados que tratan de tan interesante pleito y que se localizan en los archivos de la Casa Ducal de Medinaceli, Ducado de Medina Sidonia y Archivo General de Simancas, uno de ellos (Sección Medinaceli, Leg. 288) sobresale por los abundantes datos que ofrece sobre los términos de las Algeciras en las últimas décadas de la Edad Media. A través de él sabemos que en el año 1445 Manuel Ordiales, alcaide de Medina Sidonia, llevó a cabo el amojonamiento de los términos de las Algeciras por encargo del Duque de Medina Sidonia, aunque el deslinde que realizó no satisfizo a los vecinos de Tarifa que consideraron favorecía al Duque, por lo que recurrieron el informe elaborado por el alcaide ante la Real Chancillería de Granada. 

En los "echos y dehesas" que eran objeto del litigio, venían desde antiguo pastando los ganados de Jerez, Medina Sidonia, Tarifa y Vejer, aunque las autoridades municipales de Tarifa alegaban que lo hacían por arrendamiento del Adelantado Mayor de la Frontera y no porque los mencionados pueblos tuvieran escrituras de propiedad sobre ellos. En 1485, por provisión real de los Reyes Católicos, dirigida al Adelantado Mayor de la Frontera y al Concejo de Tarifa (ilustración que se adjunta), doña Isabel y don Femando instan a esta ciudad a que restituya los "echos e campos" de las Algeciras que tenían ocupados desde antiguo a la ciudad de Gibraltar. 

Los "echos" y dehesas motivo de la enconada controversia eran los siguientes: Arroyo de Cuevas, Arroyo de las Culebras, Nava Fría, Cabeza de las Habas, El Aciscal, El Pedregoso y El Arráez. Los Reyes Católicos exigen la devolución a Gibraltar de estos "echos e campos" y, además, que paguen los de Tarifa los frutos y rentas que los dichos "echos" hayan rendido durante los años que estuvieron en poder de aquella ciudad o 300.000 maravedíes por cada año que lo aprovecharon. En la actualidad esos "echos" pertenecen a la ciudad de Tarifa.  

En el año 1469, dueño ya el Duque de Medina Sidonia de la ciudad de Gibraltar, procedió al repartimiento de las dehesas y tierras de labor de sus términos (en su mayor parte términos de la antigua Algeciras). Dice Ignacio López de Ayala que "el Duque repartió los términos entre los vecinos que había y muchos que de nuevo se vinieron a establecer en ella (en Gibraltar); separó dehesas y baldíos en estos términos y en los de Algeciras, que ya gozaban". El reparto de tierra se hizo entre los criados del Duque a razón de una o media caballería, aunque, según testimonios posteriores, éstos "nunca las rompieron ni gozaron de ellas ni viven en la ciudad". El total de lo repartido entre 1469 y 1502 ascendió a ciento cincuenta y nueve caballerías de cuarenta fanegadas de sembradura cada una.  

Con el fin de promover el repoblamiento del término, o quizás con la esperanza de ver restaurada la ciudad de Algeciras, en 1462, Enrique IV solicitó al Papa la erección de dos abadías seculares o colegiales en las iglesias de Algeciras y Gibraltar, proyecto que se vio obstaculizado por la oposición del obispado de Cádiz. 

Tras una larga pugna entre la Corona y el Duque de Medina Sidonia, por fin y con el advenimiento del siglo XVI, Gibraltar con sus términos pasó a ser definitivamente ciudad de realengo. En 1502, los Reyes Católicos ordenaron la realización de un detallado estudio para proceder a un nuevo repartimiento de su amplio y rico término, estudio que realizaría el funcionario real Fernando de Zafra. En junio de aquel año, Zafra remitió a los reyes un memorial después de haber realizado un minucioso estudio de las tierras del término. En dicho memorial se relacionan las tierras que podían repartirse entre los nuevos vecinos, el valor de las mismas y las posibles rentas que podrían aportar a la Corona y al concejo gibraltareño. Entre los "echos" más ricos y de mayor extensión enumera los siguientes: Ojén, Getares, Navas, Zanona y Benarax (Archivo General de Simancas, Casa Real, Leg. 47).  

Paisaje, probablemente de los entornos de Algeciras, en el Libro de la Montería de Alfonso XI, 1346

Sabemos que en los primeros años del siglo XVI, la vega del río de la Miel se dedicó a la siembra y producción de caña de azúcar. La plantación pertenecía al marqués de Cádiz y a otros dos caballeros de Sevilla. Sin embargo, este cultivo debió ser abandonado, ya que los vecinos de Gibraltar se querellaron contra el marqués de Cádiz, alegando que "han tomado y ocupado y tienen sembrada de cañas duces todas las vegas del río de la Miel que es en Algeciras" (Real Chancillería de Granada, Cab. 503, Leg. 558). Los vecinos se quejaban de que con las cañas de azúcar se ocupaban los vados del río por donde debía pasar el ganado, y, también, porque se dedicaban a la caña tierras que entendían se debían dedicar a sementera. El pleito debió fallarse a favor de los vecinos, pues no vuelve a encontrarse ninguna mención con posterioridad.  

A pesar de los esfuerzos de granadinos y castellanos por mantener activa una ciudad y poblados unos términos de tanta importancia estratégica, Algeciras iba a permanecer destruida por espacio de unos trescientos veinticinco años, hasta que las circunstancias políticas y militares de la nación posibilitaran su resurgimiento. Cuando en el año 1704 la escuadra anglo-holandesa se apoderó de Gibraltar, los vecinos de aquella ciudad la abandonaron para buscar refugio en su término, dando origen a las poblaciones de San Roque, Los Barrios y la nueva Algeciras. 

Cuando, en torno a 1530, el viajero Pedro de Medina cruzó el solar de Algeciras, nos dejó la siguiente descripción de lo que quedaba de la ciudad: "Parecen en ella pedazos de muy hermosos edificios, en especial algunas torres de la cerca bien fuertes, a las cuales llega el mar. Tenía esta ciudad campos y dehesas de yerba donde se crían de los mejores ganados vacunos de España, que se llaman ahora campos de Tarifa".