La conquista de Ceuta por Portugal, en 1415, llevó al monarca Juan I de Avis a solicitar de la Santa Sede su elevación a diócesis episcopal, convirtiéndose la mezquita aljama en su nueva Catedral. A finales del siglo XVII su estado ruinoso obligó a su demolición, siendo encargada la traza de la nueva al ingeniero Juan de Ochoa. Su primera piedra fue puesta en 1686 y su consagración tuvo lugar en 1721, dado que durante buena parte de esos años la ciudad estuvo bajo asedio y el edificio fue destinado a acuartelamiento.

En un principio la planta era, como ahora, de tres naves, pero con tres capillas rectas en su cabecera. Tenía el coro a la entrada y en su fachada destacaba una pequeña torre lateral y la portada tallada en serpentina a finales del siglo XVII en la misma Ciudad.

Entre 1948 y 1958 el arquitecto municipal transformó su cabecera con otra a la romana, con deambulatorio, trasladó la capilla del Sagrario a la nave de la derecha y el coro al presbiterio, completándose su sillería con nuevas piezas de talla. Además, el interior se enriqueció con nuevas vidrieras, pinturas y relieves. La nueva fachada fue encargada al arquitecto Hermenegildo Bracons Huguet, que conservó la portada pero dándole un nuevo aire al sustituir la torre campanario original por otras dos, a cada lado de la entrada principal.

En su interior destacan su amplitud y luminosidad, que enriquecen las vidrieras de La Veneciana de Zaragoza y Maumejean de Madrid. La cúpula del crucero se decoró en la transformación de Blein con frescos del pintor bonaerense José Martín Ocaña y los relieves del escultor Bonifacio López Torvizco.

Entre sus retablos destacan el barroco y dorado de la Capilla del Sagrario, con las armas del obispo Andrés Mayoral, de mitad del siglo XVIII, y el de San Pedro Apóstol, de comienzos del XVII, procedente de la Parroquia de los Remedios.

Piezas destacadas de imaginería son las tallas de San Sebastián del siglo XVI, San Pedro y Santa Catalina del siglo XVIII, San Francisco de Asís, del XIX, y contemporáneas como Santa Beatriz de Silva, María Santísima de la Caridad, Nuestro Padre Jesús de la Flagelación, el Santísimo Cristo del Buen Fin y el Santísimo Cristo del Triunfo.

El conjunto de pinturas del templo tiene piezas de gran valor como el Tríptico Eucarístico del siglo XVII y los grandes lienzos de altar de Santo Tomás de Villanueva y San Ildefonso de Toledo de Lorente Germán del siglo XVIII, a las que se suman otras, de la misma centuria, dedicadas a San Daniel y Compañeros Mártires, patronos de Ceuta, Santa Teresa de Jesús, La Magdalena, La Piedad, La Anunciación y La Adoración de los Magos, a las que sumaron, en el siglo XIX la galería de retratos de prelados, obra del Ricardo Escribano, y en el siglo XX, los cuatro óleos de temática histórica obra del pintor Miguel Bernardini y Jaramillo.

Completan el patrimonio del templo la orfebrería, con piezas destacadas como el templete para la Custodia del Corpus Christi, del siglo XVIII, así como custodias, cálices, copones, y otras piezas de los siglos XVII al XX. También es destacable la pequeña colección de indumentaria, con ternos, capas y casullas que van del siglo XVII al XX, así como sus fondos bibliográficos y archivísticos.