El Baluarte de Nuestra Señora de la Soledad fue construido a fines del siglo XVII y es el más grande de los ocho baluartes que forman parte de la muralla edificada para defender la villa de San Francisco de Campeche contra los piratas. La construcción del inmueble concluyó en 1692 y se bautizó con el nombre de la Virgen de la Soledad, la protectora de los marinos. En 1999, la ciudad de Campeche fue designada como Patrimonio Cultural de la Humanidad por la Unesco con el título de "Ciudad Histórica Fortificada".

En 1896 el edificio se encontraba en ruinas; más adelante, durante la Revolución, el Baluarte se restauró parcialmente y se usó como bodega por las tropas federales y por el gobierno estatal. A partir de 1929 quedó bajo la jurisdicción de la Secretaría de Guerra, dependencia que lo destinó para ser habitado por familias de algunos oficiales, convertido en una vecindad.

En 1937 se inició su restauración completa, y en 1958 se convirtió en la sede del Museo Arqueológico de Campeche. Para 1975 este espacio cambió su contenido y fue reinaugurado como Museo de Historia Colonial. Una nueva intervención, en 1985, lo transformó en el Museo de las Estelas, y finalmente en 2005 se enfocó en aspectos constructivos prehispánicos, reinaugurado como Museo de Arquitectura Maya.

Uno de los detalles más interesantes del museo es la explicación del funcionamiento de la escritura maya y la traducción de textos epigráficos (los esculpidos en piedra, y los grabados en madera o metal) localizados en varios de los elementos arquitectónicos ahí exhibidos, lo que permite al visitante tener una idea del desarrollo de esta materia durante el periodo Clásico (250-1000) y conocer los contenidos de algunos de los complejos glifos mayas. Otro aspecto es la diferenciación de los elementos arquitectónicos presentes en el museo, que permiten al visitante reconocer los detalles que caracterizan a los edificios de cada una de las regiones que conforman el panorama arqueológico del estado de Campeche: Petén Norte, Río Bec, Chenes y Puuc.