El museo fue inaugurado el 1 de noviembre de 1984, sin embargo la edificación —considerada monumento emblemático de la ciudad— fue construida a finales del siglo XVI, y en el siglo XVII se estableció como defensa, aduana, almacén y único muelle autorizado por la Corona española para realizar actividades portuarias. Durante el siglo XIX y primera mitad del siglo XX, el recinto fue utilizado como Arsenal de la Nación y presidio.

En 1961, por decreto presidencial, el Instituto Nacional de Antropología e Historia tomó custodia del inmueble. En 1980, se inició el Proyecto Integral para el Rescate y Restauración de la Fortaleza, y en 2012 concluyó una de las etapas más importantes: la rehabilitación de la Plaza de Armas y la apertura de un nuevo museo en el edificio denominado Casa del Gobernador, ubicado en el lado oriente de la Plaza de Armas.

El acervo en exhibición está compuesto por bienes arqueológicos e históricos del estado. El recorrido por este espacio se plantea conforme a dos temáticas: la arqueología de la región del Golfo de México, con más de 200 piezas que dan testimonio del desarrollo cultural alcanzado por las antiguas civilizaciones; y la historia del Fuerte de San Juan de Ulúa, en el que se narra el arribo de los españoles al islote de Tecpan Tlayácac en 1518, las transformaciones del islote para su edificación y los ataques de los piratas al puerto de Veracruz durante el virreinato.

Cuenta con tres salas de exhibición permanentes:

Dos salas de arqueología dedicadas a las antiguas culturas del Golfo, al entorno natural, al culto al cuerpo, al juego de pelota, a los dioses y ritos, a la colección Manatí y al comercio.

Una sala histórica en la que se aborda el primer contacto con los españoles, la piratería, los ingenieros militares, las rutas marítimas y la época del Arsenal Nacional.

Cuenta con una sala de exhibición temporales:

• En este sitio se presentan principalmente exposiciones itinerantes de la Coordinación Nacional de Museos y Exposiciones del INAH, así como de otras instituciones públicas.

1 de noviembre de 1984