El edificio se encuentra sobre lo que fuera la Real Fortaleza de Don Juan Baltasar de Austria, construida por el gobernador Fernando Ortiz de Zárate en 1594 en las entonces abarrancadas orillas del Río de la Plata. La fortaleza fue demolida parcialmente en la década de 1850 para construir en su lugar el edificio de la Aduana Nueva, proyecto del arquitecto inglés Edward Taylor.

En 1884 las restricciones de espacio disponible en el edificio eran ya evidentes, y se planea unificar los edificios proyectados por Aberg y Kihlberg y destinarlos exclusivamente a la función de gobierno. Así, se encomienda la tarea al arquitecto italiano Francesco Tamburini. Este proyectó la unión de los edificios gemelos mediante un gran arco monumental, que hoy constituye el acceso sobre la calle Balcarce y cuya construcción comenzó en 1886, seguido por la ampliación del edificio sobre la calle Rivadavia, terminada hacia 1890. Esto marcó el fin de lo que quedaba del antiguo Fuerte, conservándose, algunos muros y una de las troneras que pueden verse en el actual Museo del Bicentenario. Siguió la expansión del palacio hacia la actual calle Yrigoyen, terminada hacia 1896, y por último la fachada este mirando a Puerto Madero, con la cual el edificio fue inaugurado oficialmente durante la segunda presidencia de Julio Roca, en 1898. Tenía en su interior “pavimentos en mosaico, columnas de mármol, molduras doradas, pinturas representando amores y asuntos mitológicos encuadrados, a lo pompeyano, en guirnaldas de flores…”.