Anales Históricos de Montevideo (1957-1968) se llamó la revista institucional del Archivo y Museo Histórico Municipal, de la cual se publicaron cinco tomos: I (1957), II (1958), III (1959), IV (1962) y V (1968). Fue un proyecto largamente reclamado por Arredondo durante su gestión al frente de la institución, que se concretó gracias al apoyo del historiador Juan Pivel Devoto cuando integró la minoría nacionalista del Concejo Departamental de Montevideo (1955-1959).
Cuatro de los cinco tomos se editaron durante la gestión y bajo la supervisión de Arredondo, quien publicó allí sus investigaciones sobre las colecciones del Archivo y Museo Histórico Municipal y otros temas relativos al patrimonio cultural del país. Cada tomo era un volumen de más de 500 páginas, con un generoso apéndice gráfico.
Los Anales reunieron numerosos estudios sobre el devenir de la ciudad, la vivienda, el transporte, el mobiliario y las artes aplicadas. La mirada era esencialmente antropológica e histórica, centrada en el desarrollo de Montevideo, con énfasis en la arquitectura y la cultura material y con la iconografía como fuente central, según el perfil dado al propio museo municipal.
El primer tomo, por ejemplo, incluyó un estudio de Arredondo sobre la vivienda montevideana y su mobiliario desde tiempos coloniales. Como en todos los temas monográficos, el texto estuvo acompañado de una importante sección gráfica, con un centenar de fotografías e ilustraciones que recogían los elementos descriptos a partir de piezas del museo y de colecciones particulares, incluida la del propio Arredondo.
Ese tomo incluyó también una reseña histórica del Museo Histórico Municipal, escrita por Arredondo, en la que el director reconoció a Pivel Devoto sus gestiones en relación con tres hitos clave de la historia del museo: la anexión del Parque Fernando García como su sección Carrasco, el traslado al edificio del Cabildo y la publicación de los Anales.
Cada tomo tuvo además una sección documental, que tenía por una parte una “Sección Archivo”, destinada a divulgar piezas de la sección Archivo de la institución, principalmente actas de la Junta Económico Administrativa de Montevideo desde 1830; y otra sección “Documentos Oficiales”, que difundió material sobre gestión del patrimonio histórico de la ciudad (por ejemplo, el traslado de la puerta de la Ciudadela, la restauración del Cabildo o la recuperación del Molino de Pérez).
Además de Arredondo, escribieron en los Anales Julio Abella Trías (sobre el Cabildo de Montevideo), Luis Bausero (historia del Palacio Legislativo), Rolando Laguarda trías (“El Río de la Plata y la Costa de Montevideo”), Fernando Assunção (“Orígenes de los bailes tradicionales”), entre otros.