Construido como baluarte defensivo, fue subiendo en altura hasta conseguir la misma cota del cerro del Cubo. Se empleó como almacén de pólvora, prisión, gabinete de meteorología, y viviendas de gente humilde hasta llegar al uso museístico actual que tiene desde mediados del siglo XX.
El Museo Histórico Militar de Melilla se encuentra en el Baluarte de la Concepción, subiendo la cuesta paralela a la muralla de Trápana o de Levante, la más antigua de la ciudad amurallada, de época renacentista. Se trata de la cota más alta en el istmo en que tras la ocupación de la ciudad un 17 de septiembre de 1497 por Pedro de Estopiñán y Virués en nombre del duque de Medina Sidonia, se constituyó el primer asentamiento de la ciudad.
El baluarte está constituido por varias partes. Posee un almacén de que en la actualidad se ha transformado en dos plantas; la lengua de Sierpe que finaliza en el citado torreón de San Sebastián; la Torre o Caballero de la Concepción y por último el antiguo cuerpo de guardia, actualmente oficinas y control de entrada del Museo y por donde se accede al patio inferior.
Desde las tres plantas exteriores, artilladas en su época, se puede apreciar una vista panorámica de la ciudad y sus alrededores, concretamente del mar Mediterráneo, de la Isla del Congreso en el Archipiélago de las Chafarinas, de la costa argelina, de los montes de Quebdana en la costa marroquí, del macizo del Gurugú desde el tómbolo del Atalayón, hasta las alturas de Sidi Hamed, Sidi Musa, Ait Aixa, el barranco del Lobo y Kola y Basbel.
