L'édifice est érigé sur d'anciennes fortifications construites par les Zianides et les Mérinides au XIIIeetXIVesiècles. Le fort fut décrit en 1505 par le Vénitien Vianelli dans le cadre des préparatifs pour la prise de Mers el-Kébir. Il en détailla la structure, les défenses, la garnison, le pont-levis et les citernes[1].
La place forte de Mers el-Kébir fut établie comme presidio et son fort fut rénové en 1514. Par la suite, il fut inspecté par Pedro Afán de Ribera et Francisco de Sotomayor afin d'organiser des améliorations dans sa construction et pour renforcer sa garnison[2]. Les travaux de 1562 furent réalisés par Giovanni Battista Calvi et Bartolomeo Quesada. La forteresse disposait de huit tours et avait une forme quadrangulaire. Elle abritait environ soixante maisons, la résidence de l'alcaide, la tour de la Cloche, la tour de la Trahison, un bastion d'artillerie, un réduit et une église. De cette époque date le fort de San Salvador, construit sur le mont San Miguel pour défendre le fort de Mers-el-Kébir, mais il fut abandonné après le siège de 1563.
Après le siège de 1563, les travaux de réparation furent confiés à Juan Bautista Antonelli, qui construisit les bastions de Santiago, San Felipe, San Juan et de la Croix. C'est à Vespasien Gonzague que l'on doit la fortification de la pointe du Calvaire, où furent installés la résidence du gouverneur, des casernes, des cours d'armes et d'autres infrastructures annexes. L'ingénieur militaire italien au service de l’Empire espagnol, Giovan Giacomo Paleari Fratino(en) intervint également dans le fort de Mers el-Kébir, en construisant le ravelin entre les bastions de Santiago et de San Felipe, où se trouvait la porte d'entrée[3].
La communication avec Oran se faisait par voie maritime et, exceptionnellement, par un chemin passant par le fort San Gregorio.
Au cours du XVIIesiècle, aucun travail de fortification ne fut entrepris. En , cette forteresse fut la dernière du double presidio de la ville d'Oran et de la ville de Mers el-Kébir à se rendre, étant ensuite occupée par la Régence d'Alger.
À partir de 1732, lors de la seconde période d'occupation espagnole, la fortification fut maintenue et de petits travaux d'aménagement furent réalisés. En 1752, José Muñoz fut chargé de l'installation d'un phare[4].
Les Français occupent Mers el-Kébir en 1831, puis agrandissent le port et le dotent du phare Saint-André en 1868. Ce dernier fut détruit en 1940, parce qu'il entravait les Anglais dans le réglage de leur tir sur les navires français[5].