Situado en la Plaza que lleva su nombre en el centro de la Ciudad, inicialmente fue construido en el siglo XV, sufriendo posteriores reformas, siendo decisiva para su conformación actual, la realizada en el siglo XVIII, cuando se colocó en la Capilla Mayor, el retablo tallado en madera y dorado en oro fino, costeado en 1752 por el Obispo de la Diócesis Martín de Barcia. En ella se encuentra la imagen de Santa María de África. Es según todas las apariencias de origen bizantina. Esta circunstancia y el hecho de que Ceuta perteneció al Imperio Romano en época de Justiniano, dió lugar a una bella leyenda. Sintetizada decía así:
"El citado emperador envió la imagen al gobernador de estos territorios, Procopio. La ciudad le estuvo rindiendo culto, hasta que se produce la invasión musulmana. En aquél entonces, -continúa refiriendo- los católicos ceutíes a fin de que no fuera profanada, la enterraron. pasó el tiempo y los portugueses reconquistaron la Ciudad. Un día a las afueras y sobre una loma, se divisa un fulgurante resplandor. Acude allí la tropa, siguiendo un gran rayo luminoso. Escarban la tierra y descubren la imagen de la Virgen que sería llamada de Santa María de África. De inmediato es trasladada procesionalmente al lugar donde después fue edificado el Santuario". La tradición hizo que al lugar se le llamara "Otero de Nuestra Señora".
La historia nos dice que la escultura fue donada por Henrique el Navegante en 1420. Al mandarla desde Lisboa, concreta: "os envío una imagen de la Virgen María, asaz devota mía" confirmando que a la misma ya se le había rendido culto antes de ser traida a Ceuta.
Henrique el Navegante pidió a cambio de esta singular donación que "cada semana, el día del sábado se diga una Misa y antes de comenzarla se pida a los asistentes en alta voz y por amor de Dios un Padrenuestro y Avemaría por mi alma". Este fue el origen de la Sabatina.
De la mano izquierda de la imagen de la Virgen cuelga un bastón de nudos. Llamado "Aleo" es con el que el primer gobernador portugués, Pedro de Meneses, jugaba, cuando le fue ofrecido el gobierno de la Plaza, por el Rey D. Juan I de Portugal. Con este trozo de abedul cuentan las crónicas que D. Pedro juró defender a Ceuta de sus enemigos.
Después de la llegada de la imagen a la ciudad, le fue ofrecido a Santa María de África. Desde entonces es tradicional que la primera autoridad militar, responsable de la defensa de este bendito trozo de tierra española, cuando se hace cargo del mando, renueve el juramento y en acto solemne que comienza en la Catedral, ofrezca el Bastón a la Reina de los Cielos.
El 10 de Noviembre de 1946, fue coronada canónicamente.
Aunque de siempre, fue considerada como patrona de la Ciudad la declaración del Patronazgo no fue hecha hasta el 24 de Noviembre de 1949 por breve Pontificio de S.S. Pío XII.
El Ilustrísimo Ayuntamiento de la Ciudad la proclamó Alcaldesa Perpetua el 5 de Marzo de 1954, razón por la que de su cuello cuelga el distintivo de Primer Regidor de la Ciudad, que éste se quita ante la Madre.
El fuego de la devoción a la Madre lo mantiene la Cofradía de Caballeros, Damas e Infantes de Santa María de África.
En otras capillas, situadas en los laterales, se encuentran otros altares dedicados a diversas imágenes, algunas de ellas pertenecientes a las Cofradías de penitencia que hacen sus salidas procesionales. A nuestro entender, destacan, el Cristo de la Vera Cruz, quizás de la misma época que la imagen de Santa María de África y la Virgen del Calvario, Dolorosa que aunque a ciencia cierta no se conoce su autor, se atribuye al sevillano del siglo XVII, Juan de Mena.
En la parte baja de lo que es la Capilla Mayor existe una cripta con enterramientos de nobles y clérigos (siglos XVIII y XIX) entre los que existe el correspondiente a una hija de los Duques de Medinaceli.
Tiene el santuario un interesante archivo y testimonio de visitantes ilustres, tal cual fue en 1950, la de Angel José Roncalli a la sazón Nuncio de S.S. en París y años después, Papa, con el nombre de Juan XXIII.