Las obras de ampliación del puerto de Málaga que se llevaron a cabo en el último cuarto del siglo XIX dejaron libres unos terrenos ganados al mar que, en virtud de una disposición de 1896, fueron entregados a la ciudad para destinarlos a parque público. Arquitectos como Eduardo Strachan, Manuel Rivera, Joaquín de Rucoba y Tomás Brioso fueron los artífices de varios proyectos que acabaron de darle su forma definitiva. Durante varios años se hicieron las obras de adecuación de los terrenos y la plantación de árboles en el espacio ganado al mar, mientras que se decidió que en el lateral norte, justo al pie de la Alcazaba, se haría un desmonte para ganar superficie que permitiera delimitar cuatro solares destinados a la construcción de edificios oficiales. El conjunto final de estos edificios, que aún hoy en día se mantienen, fue conocido popularmente por los malagueños como el ABC por acoger al Ayuntamiento, el Banco de España y Correos.

Fue en 1904 cuando comenzó la demolición del Haza Baja de la Alcazaba y que supuso, según el historiador Víctor Heredia, la desaparición de parte de la muralla medieval, de la Comandancia de Ingenieros y del Cuartel de Levante, entre otras instalaciones militares dispuestas en esta parte del recinto defensivo. Así quedaron delimitadas la calle Guillén Sotelo, con un enorme muro de contención del monte, y la avenida de Cervantes, vía paralela al Parque. La primera edificación fue la denominada Casita del Jardinero Mayor, obra de Manuel Rivera Vera, de 1911, que aprovechaba un solar triangular entre la Aduana y el Parque.

De las cuatro parcelas resultantes de la demolición del Haza Baja el primer solar en edificarse fue el que ocupó el llamado entonces Palacio Municipal, y después la Casona del Parque. La primera piedra del Ayuntamiento se colocó a finales de 1911 y fue inaugurado en 1919 gracias a un proyecto que fue diseñado por Fernando Guerrero Strachan y Manuel Rivera Vera.

El segundo edificio fue el que aparece en la imagen, la sede de Correos y Telégrafos. Su construcción responde a un programa gubernamental para dotar a las oficinas provinciales de Correos de sedes dignas y representativas, empleando estilos nacionales. El ganador del concurso en el caso malagueño fue el arquitecto vasco Teodoro Anasagasti, que proyectó entre 1916 y 1917 un inmueble neomudéjar con referencias a la cercana Alcazaba. Las obras tardaron en iniciarse varios años, y finalmente el edificio se levantó entre 1924 y 1925, y fue el 8 de septiembre de este último año cuando Correos recibió el edificio. Según el experto, "se trata de una construcción que aúna modernidad y regionalismo y en la que se emplean materiales diversos que le proporciona una variada riqueza de colores y texturas". Fue, además, el primer edificio de la ciudad en contar con una puerta giratoria en su entrada.

El inmueble quedó sin uso a finales de los 80, cuando se inauguró la nueva sede de Correos en la avenida de Andalucía. Después de años de abandono, fue rehabilitado en el año 2002 para albergar la sede del Rectorado de la Universidad de Málaga. Remodelado por completo, en su interior se pueden contemplar varias piletas de garum (salsa realizada a base de vísceras de pescado), pertenecientes a una factoría romana de salazones instalada a los pies del cerro de la Alcazaba que exportaba su producción a la capital del Imperio, y restos de murallas del tiempo de los fenicios y de los siglos XI-XIV, que se corresponde con el puerto.