La historia del museo se divide en tres períodos.
De 1940 a 1956
La Colección museográfica de La Legión en Ceuta inicia su andadura en 1.940 cuando, tras la finalización de la Guerra Civil Española, comienzan a reunirse en el Acuartelamiento de Dar-Riffien las banderas, los guiones, los uniformes y las armas tanto del Cuerpo como capturadas al enemigo en las campañas de Marruecos (1920-1927), los Sucesos Revolucionarios de Asturias y Cataluña (octubre 1934) y la Guerra Civil Española (1936-1939).
De 1956 a 1979
Con la independencia del Reino de Marruecos, el museo de La Legión se traslada al Acuartelamiento de El Serrallo, sede de la Plana Mayor de Mando del Tercio “Duque de Alba” 2º de La Legión. Al estar situado en el interior del acuartelamiento que además se encuentra considerablemente alejado del centro de la ciudad, en esta época la colección solamente fue accesible a visitas oficiales y no al público general.
De 1979 a la actualidad
En 1.974, siendo Coronel Primer Jefe del Tercio “Duque de Alba”, 2º de La Legión el Ilmo. Sr. Don José Giménez Henríquez, se hizo una importante donación de fondos por parte del Ministerio de la Vivienda, cuya cartera ostentaba el Ilmo. Sr. Don José Utrera Molina que permitió levantar el edificio que alberga actualmente el Museo.
Tras su traslado a su actual ubicación fue inaugurado en julio de 1979 con la asistencia del Excmo. Sr. Teniente General D. Pedro Merry Gordon (Capitán General de la 2ª Región Militar), el Excmo. Sr. D. José Giménez Henríquez (General Subinspector de La Legión) y el Ilmo. Sr. D. Antonio Eleta Sequera (Coronel Primer Jefe del Tercio “Duque de Alba”, 2º de La Legión).