Una vez conquistada la ciudad de Algeciras a los musulmanes en marzo del año 1344 por el rey de Castilla, Alfonso XI, con la inestimable colaboración y activa participación de la Corona de Aragón, la Señoría de Génova, el Papado de Aviñón -que concedió a la empresa militar los beneficios económicos y espirituales declarándola Santa Cruzada-, los reyes de Francia e Inglaterra y las numerosas huestes aportadas por los centenares de cruzados alemanes, franceses, ingleses, portugueses e italianos que acudieron al cerco de la ciudad, el monarca castellano puso todo su interés en el repartimiento y la repoblación del término municipal, consciente de que si quería conservar aquel importante enclave portuario del lado de la Cristiandad, rodeado, como estaba, de tierras del Islam (Gibraltar, Castellar, Jimena y Estepona en esta orilla, y Ceuta y Tánger, en la otra) era necesario dotarla de un fuerte contingente militar, pero, sobre todo, hacer que la repoblación del territorio recién conquistado se consolidara y que, como se exigía a los que fueron favorecidos con casas, comercios, tierras de cultivo, mezquitas, alhóndigas, baños, hornos y molinos harineros, permanecieran residiendo en la ciudad, al menos, durante diez años; condición que debió cumplir la gente del común, pero no los miembros de la nobleza beneficiada en el reparto, pues en las Crónicas de la época se hace referencia a cómo los grandes señores del reino, que recibieron importantes donaciones en la ciudad, nunca fueron a establecerse ni a residir en ella, quedando sin roturar la tierra y sin actividad los comercios y otros establecimientos que les habían correspondido en el reparto, lo que favoreció su despoblación.

Abandonado, a causa de la guerra civil entre petristas y trastamaristas, el abastecimiento de la ciudad y con muy escasa guarnición militar, Algeciras sería reconquistada por los nazaríes en el mes de octubre del año 1369.

Pero, en el mes de marzo de 1344, el rey de Castilla quiso seguir los pasos de su bisabuelo, el rey Fernando III, que una de sus primeras acciones después de haber tomado Sevilla en el año 1248, fue instaurar la archidiócesis hispalense con el fin de atraer hombres de religión que se ocuparan de las mezquitas consagradas como iglesias, así como frailes que fundaran conventos y monasterios y que, de paso, atrajeran repobladores que fijaran su residencia en la ciudad.

Folio de uno de los traslados de la bula de 1380 (Archivo de la Catedral de Cádiz).

Después de los fastos y celebraciones que siguieron a la entrada de los cristianos en Algeciras, consagrada la mezquita aljama como iglesia y entronizada en ella la imagen de Santa María de la Palma, el rey de Castilla debió recibir al arzobispo de Toledo y Primado de las Españas, don Gil de Albornoz, y al obispo de Cádiz, don Bartolomé. Sería el primero de ellos el que plantearía al rey cómo hacer la petición al Santo Padre el Papa para que se creara una nueva diócesis en aquella ciudad, heredera del primer obispado instaurado en la bahía de Algeciras en época romana: el de Carteia, con su obispo San Hiscio.

Alfonso XI, quizás aconsejado por el arzobispo de Toledo, o por propia iniciativa, ordenó al caballero García Fernández de Boneso que preparara una embajada que debía viajar hasta Aviñón con una carta para el papa Clemente VI en la que le relataba lo acaecido durante el cerco, cómo se habían consagrado las mezquitas a la fe cristiana y portara, también, como regalo, varios de los pendones enemigos tomados en la batalla del río Palmones. La carta la redactó el secretario del rey y notario mayor de Castilla, don Fernán Sánchez de Valladolid, y en ella se incluía la petición de Alfonso XI de que erigiera en catedral la que había sido mezquita mayor, consagrada como iglesia de Santa María de la Palma. Y que, si lo tenía a bien, la hiciera diócesis episcopal, como lo era Cádiz y, antes, lo fueron las ciudades de Asidonia y Carteia.

Grabado que representa al papa Clemente VI realizado en el año 1678.

El rey y su Corte marcharon a Sevilla a mediados del mes de abril, una vez realizado el repartimiento de la ciudad y nombrado los doce regidores y los cuatro fieles que formarían el Concejo municipal que habrían de gobernar Algeciras, con su alcalde mayor, don Álvar García de Illas.

Se hallaba en el alcázar sevillano cuando llegó a la ciudad un legado del papa Clemente VI que portaba una carta del Santo Padre. En ella le comunicaba a Alfonso XI que el día 30 de abril había aprobado y sellado la bula, titulada Gaudemus et exultamus, por la que erigía una diócesis en Algeciras que se denominaría Gadicensis et Insula Viridis (De Cádiz y de la Isla Verde), aunque unida canónicamente a la de Cádiz. En la misma carta le comunicaba que había nombrado a fray Bartolomé, hasta ese día obispo de Cádiz, titular de la sede de Algeciras, con la condición de que, a partir de su nombramiento, pasara a residir en esa ciudad.

Como el Papa era conocedor de las tensiones y enfrentamientos existentes entre la diócesis de Cádiz y el arzobispado de Sevilla, nombró como ejecutor de la bula de fundación de la nueva sede episcopal a los arzobispos de Toledo, don Gil de Albornoz, y de Santiago, don Pedro V, con el mandato de que organizaran y dotaran de personal y bienes muebles a la nueva diócesis con la aportación económica que el rey les proveyese.

Hoy es posible avanzar la hipótesis de por qué el Papa, en su bula, creó la nueva diócesis de Algeciras, pero "unida canónicamente a la de Cádiz" y no desvinculada de ella, cuando existía un antecedente relevante en la zona, como era el obispado de Carteia. Es posible que la cercanía del obispo de Cádiz, don Bartolomé, al rey de Castilla y su participación en la toma de Algeciras, influyeran en la decisión del Papa de Aviñón. No es baladí pensar en esa posibilidad, puesto que el mismo don Bartolomé sería nombrado el primer obispo de la diócesis de Algeciras, aunque con la obligación de trasladar su residencia a la Insula Viridis.

La copia más antigua de esta bula se encuentra inserta en otra bula de Clemente VII que certifica la del anterior pontífice, fechada el 22 de septiembre del año 1380 (publicada y traducida por Luis Charlo Brea y María Belén Piqueras García) y, que entre otras cosas dice: “Queriendo también asentir a las súplicas y piadosos deseos del rey (Alfonso XI), después de diligente deliberación sobre tales asuntos con nuestros hermanos, venimos a erigir, con la plenitud de la potestad apostólica, para alabanza y gloria de Dios y de Santa María, la Virgen gloriosísima y para provecho de las almas, aumento del culto divino y exaltación de la fe católica, como ciudad por autoridad apostólica a la citada villa, llamada en latín Isla Verde y en árabe Algeciras, en otro tiempo localizada en la diócesis de Cádiz, lugar en verdad noble e importante y dotado de muchas ventajas, y la distinguimos con el título de ciudad, erigimos en catedral a dicha iglesia de Santa María (de la Palma), otrora templo de horror, y decretamos que ella sea para siempre Iglesia Catedral de dicha ciudad, y unimos con la citada autoridad tanto a ella como a la iglesia de Cádiz, y con dicha autoridad establecemos que nuestro venerable hermano Bartolomé, obispo gadicense, a quien también hemos puesto al frente como obispo y pastor de la iglesia de Algeciras, y cualquier otro sucesor, que presidiera a dichas iglesias así unidas, se llame para siempre obispo de Cádiz y de Algeciras, proponiéndonos hacer que se ordene dicha iglesia de Algeciras con canónigos, racioneros, y otros ministros y servidores, según dote que el rey le asignará y otros réditos propios, que la iglesia percibirá y tendrá en la ciudad de Algeciras y en su territorio para su propio decoro y para ejercer allí el culto del divino nombre. Dada en Aviñón a 30 de abril en el segundo año de nuestro Pontificado”.

Pasados varios meses, el día 19 de julio del año 1344, el papa Clemente VI otorgó otra bula, titulada Respersit rore gaudiorum, por la que elevaba a rango de catedral la iglesia de Santa María de la Palma de Algeciras.

Imagen de la Virgen de la Merced, patrona de Jerez, que, según la tradición mercedaria, procede del convento de esa Orden fundado en Algeciras en el año 1345.

Tras el establecimiento del obispado en la ciudad, la vida religiosa algecireña se vio pronto enriquecida con la fundación de un convento de la Orden de la Merced en una antigua mezquita menor que el rey había mandando consagrar como iglesia bajo la advocación de San Hipólito. También se fundó, en el año 1345, un monasterio Franciscano con algunos frailes procedentes del convento de Sevilla, a los que el rey les donó una casa en la ciudad con la doble misión de repoblar y evangelizar. Igualmente se estableció en Algeciras una encomienda de la Orden de Santiago.

Pero los proyectos de repoblación que el rey Alfonso XI había planeado para hacer de Algeciras y su puerto el enclave desde el que continuar la reconquista del reino de Granada, fracasaron. Muerto este rey en 1350, cuando ponía cerco a Gibraltar, víctima de la Peste Negra, desasistida de tropas la ciudad, sin galeras que la defendieran desde el mar y desabastecida su escasa población a causa de la guerra civil que enfrentaba al rey Pedro I con su hermanastro Enrique de Trastámara, cuando el rey murió a manos de su hermano en Montiel, en octubre del año 1369, el sultán de Granada, aprovechando el vacío de poder, con un renovado ejército y la ayuda de la flota meriní atacó la ciudad, teniendo sus defensores que rendirla tras un breve asedio de tres días. El cabildo catedralicio hubo de abandonar Algeciras sin el obispo, que se hallaba ausente en esos días. Llevaron consigo los libros de solfa, los objetos litúrgicos que pudieron salvar y la imagen de la Virgen de la Palma. Los canónigos se refugiaron, primero en Medina Sidonia, pensando que pronto retornarían a su ciudad. Pero como ese feliz acontecimiento nunca se hizo realidad, finalmente se trasladaron a Cádiz en tiempos de don Enrique, I Duque de Medina Sidonia, hacia el año 1390.